sachin26

Posted on

# 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;

}
}