Striver's SDE Sheet Journey - #19 Two sum

Problem Statement :-

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Example

Input : nums = [2,7,11,15], target = 9

Result : [0,1]

Explanation : Because nums[0] + nums[1] == 9, we return [0, 1].

Solution 1

we can solve this problem by using two pointer approach
lets discuss this solution step by step.

step-1 make a copy sortArr array from the nums array.

step-2 sort the copy sortArr array.

step-3 initialise two pointers start=0, end=n.

step-4 run a loop from start to end and then,

1. calculate the sum from start & end indices of array.

2. break the loop if sum == target

3. increase the start by 1 if sum < target

4. decrease the end by 1 if sum > target

step-5 find the original indices from nums array & return it.

Dry Run
nums = [1,3,5,2,7] , target = 4

1. copy the array.
copyArr = [1,3,5,2,7]

2. sort the copied array.
copyArr = [1,2,3,5,7]

3. run two pointers on sorted array

copyArr = [1,2,3,5,7]
           |       |
        start      end

sum = start + end
sum = 1 + 7 => 8
8 > target = 4 ----> end--

copyArr = [1,2,3,5,7]
           |     |
        start    end

sum = start + end
sum = 1 + 5 => 6
6 > target = 4 ----> end--

copyArr = [1,2,3,5,7]
           |   |
        start  end

sum = start + end
sum = 1 + 3 => 4
4 == target = 4 --> stop the loop

return the original indices of values from the nums array.

           0 1 2 3 4
copyArr = [1,2,3,5,7]
           |   |
        start  end

        0 1 3 4 5
nums = [1,3,5,2,7]

ans = [0,1]

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {

        int[] sortArr = nums.clone();
        int[] ans = new int[2];

        Arrays.sort(sortArr);

        int start =0, end = nums.length-1;
        int n1 = 0,n2 = 0;

        while(start < end){

            int sum = sortArr[start] + sortArr[end];

            if(sum == target) {
                n1 = sortArr[start];
                n2 = sortArr[end];
                break;
            }else
             if(sum > target)
                  end--;
              else
                start++;
        }

        for(int i=0; i<nums.length; i++){

            if(n1 == nums[i]){
                ans[0] = i;
                n1 = -1;
            }
            else
            if(n2 == nums[i]){
                ans[1] = i;
                n2 = -1;
        }}


        return ans;



    }
}

Blog

Striver's SDE Sheet Journey - #19 Two sum

sachin26

Solution 1

Java

Join Our Newsletter. No Spam, Only the good stuff.

Related