Two Sum II - Input Array Is Sorted

🎯

Two Sum II - Input Array Is Sorted

easyTWO_POINTERAmazonGoogleMicrosoft

Imagine you have a sorted list of prices and want to find two items that add up exactly to your gift card balance.

💡 This problem is about finding two numbers in a sorted array that sum to a target. Beginners often struggle because they try brute force without leveraging the sorted property, missing the efficient two-pointer technique.

📋

Problem Statement

Given a 1-indexed array of integers 'numbers' that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers (index1, index2) as an integer array [index1, index2] of length 2, where 1 <= index1 < index2 <= numbers.length. You may assume that each input would have exactly one solution and you may not use the same element twice.

1 ≤ numbers.length ≤ 10^5-1000 ≤ numbers[i] ≤ 1000numbers is sorted in non-decreasing order-1000 ≤ target ≤ 1000

💡

Example

Input"numbers = [2,7,11,15], target = 9"

Output[1, 2]

2 + 7 = 9, so return indices 1 and 2.

Input"numbers = [2,3,4], target = 6"

Output[1, 3]

2 + 4 = 6, so return indices 1 and 3.

Input"numbers = [-1,0], target = -1"

Output[1, 2]

-1 + 0 = -1, so return indices 1 and 2.

• Array with only two elements → must return [1, 2]
• Target is sum of first and last elements → test two-pointer extremes
• All elements are the same and target is twice that element → test duplicates
• No valid pair (not possible per problem statement, but consider robustness)

⚠️

Common Mistakes

Using 0-based indices in output instead of 1-based

Wrong answer due to off-by-one error

✅ Add 1 to indices before returning

Not moving pointers correctly when sum < or > target

Infinite loop or incorrect result

✅ Increment left pointer if sum < target, decrement right pointer if sum > target

Using binary search on entire array instead of subarray after current element

May find same element twice or incorrect pair

✅ Start binary search from i+1 to avoid duplicates

Not handling edge case of array length 2

May fail or return empty result

✅ Ensure loops and pointers handle minimum length arrays

🧠

Brute Force (Nested Loops)

💡 Brute force is the foundation; it helps understand the problem by checking all pairs, though it's inefficient for large inputs.

Intuition

Try every possible pair of numbers to see if they sum to the target.

Algorithm

1. Iterate over each element as the first number.
2. For each first number, iterate over the subsequent elements as the second number.
3. Check if the sum of the two numbers equals the target.
4. If yes, return their 1-based indices.

💡 Nested loops are straightforward but can be slow; understanding this helps appreciate the need for better methods.

</>

Code

def two_sum_brute(numbers, target):
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]
    return []

# Driver code
if __name__ == '__main__':
    print(two_sum_brute([2,7,11,15], 9))  # Output: [1, 2]

Line Notes

for i in range(n):Outer loop picks the first number to pair

for j in range(i + 1, n):Inner loop picks the second number after the first

if numbers[i] + numbers[j] == target:Check if current pair sums to target

return [i + 1, j + 1]Return 1-based indices as required by problem

import java.util.*;
public class TwoSumBrute {
    public static int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{i + 1, j + 1};
                }
            }
        }
        return new int[0];
    }
    public static void main(String[] args) {
        int[] result = twoSum(new int[]{2,7,11,15}, 9);
        System.out.println(Arrays.toString(result)); // [1, 2]
    }
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop selects first element

for (int j = i + 1; j < n; j++) {Inner loop selects second element after first

if (numbers[i] + numbers[j] == target) {Check if sum matches target

return new int[]{i + 1, j + 1};Return indices adjusted for 1-based indexing

#include <iostream>
#include <vector>
using namespace std;

vector<int> twoSumBrute(vector<int>& numbers, int target) {
    int n = numbers.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (numbers[i] + numbers[j] == target) {
                return {i + 1, j + 1};
            }
        }
    }
    return {};
}

int main() {
    vector<int> nums = {2,7,11,15};
    vector<int> res = twoSumBrute(nums, 9);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // [1, 2]
    return 0;
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop picks first number

for (int j = i + 1; j < n; j++) {Inner loop picks second number after first

if (numbers[i] + numbers[j] == target) {Check if pair sums to target

return {i + 1, j + 1};Return 1-based indices as vector

function twoSumBrute(numbers, target) {
    const n = numbers.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (numbers[i] + numbers[j] === target) {
                return [i + 1, j + 1];
            }
        }
    }
    return [];
}

// Test
console.log(twoSumBrute([2,7,11,15], 9)); // [1, 2]

Line Notes

for (let i = 0; i < n; i++) {Outer loop selects first element

for (let j = i + 1; j < n; j++) {Inner loop selects second element after first

if (numbers[i] + numbers[j] === target) {Check if sum equals target

return [i + 1, j + 1];Return indices adjusted for 1-based indexing

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, resulting in n*n operations.

💡 For n=20, this means up to 400 checks, which is manageable but grows quickly for larger n.

Interview Verdict: Accepted but inefficient for large inputs

This approach works but is too slow for large arrays, motivating better methods.

🧠

Two Pointers (Opposite Ends)

💡 This approach leverages the sorted property to find the pair in linear time by moving two pointers inward.

Intuition

Start with one pointer at the beginning and one at the end; move pointers based on sum compared to target.

Algorithm

1. Initialize left pointer at start and right pointer at end.
2. Calculate sum of elements at pointers.
3. If sum equals target, return their 1-based indices.
4. If sum is less than target, move left pointer right to increase sum.
5. If sum is greater than target, move right pointer left to decrease sum.
6. Repeat until pointers meet.

💡 The key is adjusting pointers based on sum comparison, which is intuitive once you understand sorted arrays.

</>

Code

def two_sum_two_pointers(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

# Driver code
if __name__ == '__main__':
    print(two_sum_two_pointers([2,7,11,15], 9))  # Output: [1, 2]

Line Notes

left, right = 0, len(numbers) - 1Initialize pointers at array ends

while left < right:Loop until pointers cross

current_sum = numbers[left] + numbers[right]Calculate sum of pointed elements

if current_sum == target:Check if sum matches target

public class TwoSumTwoPointers {
    public static int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[0];
    }
    public static void main(String[] args) {
        int[] result = twoSum(new int[]{2,7,11,15}, 9);
        System.out.println(java.util.Arrays.toString(result)); // [1, 2]
    }
}

Line Notes

int left = 0, right = numbers.length - 1;Initialize pointers at array ends

while (left < right) {Loop until pointers cross

int sum = numbers[left] + numbers[right];Calculate sum of elements at pointers

if (sum == target) {Check if sum matches target

#include <iostream>
#include <vector>
using namespace std;

vector<int> twoSumTwoPointers(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return {left + 1, right + 1};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return {};
}

int main() {
    vector<int> nums = {2,7,11,15};
    vector<int> res = twoSumTwoPointers(nums, 9);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // [1, 2]
    return 0;
}

Line Notes

int left = 0, right = numbers.size() - 1;Initialize pointers at array ends

while (left < right) {Loop until pointers cross

int sum = numbers[left] + numbers[right];Calculate sum of elements at pointers

if (sum == target) {Check if sum matches target

function twoSumTwoPointers(numbers, target) {
    let left = 0, right = numbers.length - 1;
    while (left < right) {
        const sum = numbers[left] + numbers[right];
        if (sum === target) {
            return [left + 1, right + 1];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return [];
}

// Test
console.log(twoSumTwoPointers([2,7,11,15], 9)); // [1, 2]

Line Notes

let left = 0, right = numbers.length - 1;Initialize pointers at array ends

while (left < right) {Loop until pointers cross

const sum = numbers[left] + numbers[right];Calculate sum of elements at pointers

if (sum === target) {Check if sum matches target

⏱

Complexity

TimeO(n)

SpaceO(1)

Each pointer moves at most n times, so total operations are linear.

💡 For n=20, this means at most 20 steps, which is very efficient.

Interview Verdict: Accepted and optimal for this problem

This approach is the best balance of simplicity and efficiency for sorted arrays.

🧠

Binary Search for Complement

💡 This approach uses binary search to find the complement for each element, leveraging sorted order but less efficient than two pointers.

Intuition

For each element, binary search for the number that complements it to reach the target.

Algorithm

1. Iterate over each element as the first number.
2. Calculate complement = target - current element.
3. Binary search for complement in the subarray after current element.
4. If found, return 1-based indices of current element and complement.

💡 Binary search reduces search time for complement from linear to logarithmic, improving over brute force.

</>

Code

def binary_search(arr, left, right, target):
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def two_sum_binary_search(numbers, target):
    n = len(numbers)
    for i in range(n):
        complement = target - numbers[i]
        j = binary_search(numbers, i + 1, n - 1, complement)
        if j != -1:
            return [i + 1, j + 1]
    return []

# Driver code
if __name__ == '__main__':
    print(two_sum_binary_search([2,7,11,15], 9))  # Output: [1, 2]

Line Notes

while left <= right:Standard binary search loop condition

mid = left + (right - left) // 2Calculate middle index to avoid overflow

if arr[mid] == target:Check if mid element is the complement

for i in range(n):Iterate over each element to find complement

public class TwoSumBinarySearch {
    private static int binarySearch(int[] arr, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    public static int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        for (int i = 0; i < n; i++) {
            int complement = target - numbers[i];
            int j = binarySearch(numbers, i + 1, n - 1, complement);
            if (j != -1) return new int[]{i + 1, j + 1};
        }
        return new int[0];
    }

    public static void main(String[] args) {
        int[] result = twoSum(new int[]{2,7,11,15}, 9);
        System.out.println(java.util.Arrays.toString(result)); // [1, 2]
    }
}

Line Notes

while (left <= right) {Binary search loop condition

int mid = left + (right - left) / 2;Calculate mid index safely

if (arr[mid] == target) return mid;Found complement at mid

for (int i = 0; i < n; i++) {Iterate over array to find complement for each element

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(const vector<int>& arr, int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

vector<int> twoSumBinarySearch(vector<int>& numbers, int target) {
    int n = numbers.size();
    for (int i = 0; i < n; i++) {
        int complement = target - numbers[i];
        int j = binarySearch(numbers, i + 1, n - 1, complement);
        if (j != -1) return {i + 1, j + 1};
    }
    return {};
}

int main() {
    vector<int> nums = {2,7,11,15};
    vector<int> res = twoSumBinarySearch(nums, 9);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // [1, 2]
    return 0;
}

Line Notes

while (left <= right) {Binary search loop condition

int mid = left + (right - left) / 2;Calculate mid index safely

if (arr[mid] == target) return mid;Found complement at mid

for (int i = 0; i < n; i++) {Iterate over array to find complement for each element

function binarySearch(arr, left, right, target) {
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

function twoSumBinarySearch(numbers, target) {
    const n = numbers.length;
    for (let i = 0; i < n; i++) {
        const complement = target - numbers[i];
        const j = binarySearch(numbers, i + 1, n - 1, complement);
        if (j !== -1) return [i + 1, j + 1];
    }
    return [];
}

// Test
console.log(twoSumBinarySearch([2,7,11,15], 9)); // [1, 2]

Line Notes

while (left <= right) {Binary search loop condition

const mid = left + Math.floor((right - left) / 2);Calculate mid index safely

if (arr[mid] === target) return mid;Found complement at mid

for (let i = 0; i < n; i++) {Iterate over array to find complement for each element

⏱

Complexity

TimeO(n log n)

SpaceO(1)

For each of the n elements, binary search takes O(log n), totaling O(n log n).

💡 For n=20, this means about 20 * 4.3 = 86 operations, better than brute force but slower than two pointers.

Interview Verdict: Accepted but less optimal than two pointers

Good alternative if two pointers are not obvious; still efficient but not best.

📊

All Approaches - One-Glance Tradeoffs

💡 Two pointers approach is best for 95% of interviews due to simplicity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Two Pointers	O(n)	O(1)	No	N/A	Code this approach
3. Binary Search for Complement	O(n log n)	O(1)	No	N/A	Mention as alternative

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify input format and indexing (1-based).State brute force approach to show understanding.Explain inefficiency and introduce two pointers leveraging sorted array.Optionally mention binary search as alternative.Code the two pointers approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 7min → Test: 3min. Total ~15min

What the Interviewer Tests

Ability to recognize sorted array property, apply two pointers, handle indexing carefully, and optimize from brute force.

Common Follow-ups

• What if the array was not sorted? → Use hash map for O(n) solution.
• What if multiple pairs sum to target? → Return any one or all pairs depending on requirement.

💡 These follow-ups test adaptability and understanding of problem constraints.

🔍

Pattern Recognition

When to Use

1) Input array is sorted, 2) Need to find two elements summing to target, 3) Output indices, 4) Exactly one solution guaranteed.

Signature Phrases

Input array is sortedFind two numbers such that they add up to target

NOT This Pattern When

Problems where array is unsorted or multiple pairs needed, which require hash maps or other techniques.

Similar Problems

Two Sum - unsorted array, use hash map3Sum - extend two pointers to three elementsTwo Sum IV - Input is a BST - similar two-pointer logic on BST

Practice

1. You are given an integer array and a target value. The task is to find all unique quadruplets in the array that sum up to the target. Which approach guarantees an optimal solution that balances time complexity and handles duplicates efficiently?

easy

A. Use four nested loops to check every quadruplet combination.

B. Use dynamic programming to build up solutions for smaller sums and combine them for quadruplets.

C. Apply a greedy algorithm that picks the largest elements first to reach the target sum quickly.

D. Sort the array, then use a hash map to store all pairs of sums and find complementary pairs without index overlap.

Solution

1. Step 1: Understand problem constraints

   Finding quadruplets summing to target requires checking combinations efficiently and avoiding duplicates.

2. Step 2: Evaluate approaches

   Brute force (four loops) is correct but inefficient. Greedy fails because sum combinations are not monotonic. DP is not suitable here. Hash map storing pairs of sums allows O(n^2) preprocessing and efficient lookup, handling duplicates by sorting and index checks.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash map approach balances efficiency and correctness [OK]

Hint: Hash map of pairs enables efficient quadruplet search [OK]

Common Mistakes:

• Thinking greedy or DP solves 4Sum efficiently

2. Consider the following code snippet implementing the Dutch National Flag algorithm. Given the input array [2, 0, 1], what is the value of mid after the first swap operation inside the while loop?

easy

A. 3

B. 2

C. 0

D. 1

Solution

1. Step 1: Trace initial pointers and first iteration

   Initially, low=0, mid=0, high=2, nums=[2,0,1]. Since nums[mid]=2, swap nums[mid] and nums[high]: swap nums[0] and nums[2]. Array becomes [1,0,2], high=1, mid remains 0.

2. Step 2: Value of mid after first swap

   After swapping 2 and 1, mid is not incremented and remains 0.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   mid does not increment after swapping 2, so mid=0 after first swap [OK]

Hint: mid increments only after swapping 0 [OK]

Common Mistakes:

• Assuming mid increments after swapping 2
• Off-by-one on mid pointer
• Confusing low and mid increments

3. What is the time complexity of the two-pointer approach that fills the output array from the end by comparing absolute values of elements at both ends of the input sorted array?

medium

A. O(n log n) due to sorting the squared array after processing

B. O(n) because each element is processed exactly once with two pointers

C. O(n²) because each comparison may involve scanning the array

D. O(n) for processing plus O(n) for extra space allocation

Solution

1. Step 1: Identify the main loop behavior

   The two-pointer approach moves pointers inward, processing each element once.

2. Step 2: Confirm no sorting or nested loops

   No sorting is done; comparisons and assignments are O(1) each, total O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear scan with two pointers -> O(n) [OK]

Hint: Two pointers process each element once -> O(n) [OK]

Common Mistakes:

• Assuming sorting is still needed -> O(n log n)
• Confusing comparisons with nested loops -> O(n²)
• Ignoring constant-time operations

4. Suppose the problem changes: you can reuse elements multiple times to form the triplet sum closest to the target. Which modification to the two-pointer approach correctly handles this scenario?

hard

A. Keep the two-pointer approach but reset pointers after each sum check to allow reuse.

B. Use three nested loops to allow repeated elements since two pointers assume unique indices.

C. Modify the two-pointer approach to allow left and right pointers to stay or move without skipping duplicates, enabling reuse.

D. Sort the array and use a hash set to store sums, then binary search for closest sum.

Solution

1. Step 1: Understand reuse requirement

   Reusing elements means pointers can stay or move without skipping duplicates, unlike standard two-pointer which assumes unique indices.

2. Step 2: Adjust two-pointer logic

   Allow pointers to move or stay to consider repeated elements, carefully updating closest sum without skipping valid reuse combinations.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Modifying pointer movement to allow reuse fits problem constraints [OK]

Hint: Allow pointers to stay or move to reuse elements [OK]

Common Mistakes:

• Using naive two-pointer without reuse
• Switching to triple loops unnecessarily
• Using hash sets without efficiency

5. Suppose the input array can contain any integer values, not just 0, 1, and 2, but you still want to sort it in a single pass using a similar three-pointer approach. Which modification to the Dutch National Flag algorithm is necessary to handle this general case correctly?

hard

A. Use counting sort instead, as three pointers only work for three distinct values

B. Extend the algorithm to dynamically partition into k segments with k pointers

C. Map the values to 0,1,2 first, then apply the original algorithm

D. Use quicksort partitioning with recursive calls instead of pointers

Solution

1. Step 1: Understand limitation of original algorithm

   The Dutch National Flag algorithm is designed specifically for three distinct values and uses three pointers to partition accordingly.

2. Step 2: Generalize to k distinct values

   For more than three distinct values, the algorithm must be extended to k pointers or multiple passes to partition into k segments, as a single pass with three pointers cannot correctly sort arbitrary values.

3. Step 3: Evaluate other options

   Counting sort is two-pass, mapping values is not always feasible, and quicksort is general but not single pass.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Generalizing requires more pointers or passes, not just three pointers [OK]

Hint: Three pointers only for three distinct values [OK]

Common Mistakes:

• Trying to map values first
• Using quicksort for single pass
• Assuming counting sort is single pass