## DEV Community is a community of 850,636 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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;

}
}
``````