Interview Sheet Q1:- 1. Two Sum

LeetCode: Two Sum

Given an array nums and a target, return indices of two numbers such that:

nums[i] + nums[j] == target

You can assume exactly one valid answer exists.

Approach 1: Brute Force

Logic

Check every possible pair in the array.

For each element:

• Compare it with all next elements
• If their sum becomes target → return indices

Time Complexity

• O(n²)

Space Complexity

• O(1)

Java Solution

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

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

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

                if(nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }

        return new int[]{};
    }
}

---

Approach 2: HashMap (Optimal)

Logic

Instead of checking all pairs:

For every number:

1. Find what number is needed to reach target
2. Check if that number already exists in HashMap
3. If yes → answer found
4. Else store current number with its index

Example:

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

Current = 7
Need = 9 - 7 = 2

2 already exists in map
So answer = [index of 2, current index]

Why HashMap?

HashMap gives:

• Fast search → O(1)
• Fast insert → O(1)

So total becomes linear.

Time Complexity

• O(n)

Space Complexity

• O(n)

Java Solution

import java.util.HashMap;

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

        HashMap<Integer, Integer> map = new HashMap<>();

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

            int need = target - nums[i];

            if(map.containsKey(need)) {
                return new int[]{map.get(need), i};
            }

            map.put(nums[i], i);
        }

        return new int[]{};
    }
}

---

Approach 3: Sorting + Two Pointers

Logic

If array is sorted:

• Small value at left
• Large value at right

Then:

• If sum is small → move left pointer
• If sum is large → move right pointer
• If equal → found

But problem asks for original indices, so we store:

• value
• original index

together before sorting.

Time Complexity

• Sorting → O(n log n)
• Two pointers → O(n)

Overall:

• O(n log n)

Space Complexity

• O(n)

Java Solution

import java.util.Arrays;

class Solution {

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

        int[][] arr = new int[nums.length][2];

        // store value and original index
        for(int i = 0; i < nums.length; i++) {
            arr[i][0] = nums[i];
            arr[i][1] = i;
        }

        Arrays.sort(arr, (a, b) -> a[0] - b[0]);

        int left = 0;
        int right = nums.length - 1;

        while(left < right) {

            int sum = arr[left][0] + arr[right][0];

            if(sum == target) {
                return new int[]{arr[left][1], arr[right][1]};
            }

            else if(sum < target) {
                left++;
            }

            else {
                right--;
            }
        }

        return new int[]{};
    }
}

For interviews, the HashMap approach is the expected optimal solution.