Two Sum II - Input Array Is Sorted - Practice Coding Problems

Two Sum II - Input Array Is Sorted - Problem

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.

Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Input & Output

Example 1 — Basic Case

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

› Output: [1,2]

💡 Note: numbers[1] + numbers[2] = 2 + 7 = 9, so return indices [1,2] in 1-indexed format

Example 2 — Later Position

$ Input: numbers = [2,3,4], target = 6

› Output: [1,3]

💡 Note: numbers[1] + numbers[3] = 2 + 4 = 6, indices are [1,3] in 1-indexed format

Example 3 — Minimum Size

$ Input: numbers = [-1,0], target = -1

› Output: [1,2]

💡 Note: numbers[1] + numbers[2] = -1 + 0 = -1, return [1,2] for minimum array size

Constraints

2 ≤ numbers.length ≤ 3 × 10⁴
-1000 ≤ numbers[i] ≤ 1000
numbers is sorted in non-decreasing order
-1000 ≤ target ≤ 1000
The tests are generated such that there is exactly one solution

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted array [2,7,11,15] and target 9

Process

Use two pointers to efficiently find the pair

Output

Return 1-indexed positions [1,2]

Key Takeaway

🎯 Key Insight: Use the sorted property with two pointers - move left pointer right if sum is too small, right pointer left if sum is too large

Asked in

a Amazon 45 M Microsoft 38 A Apple 32 G Google 28

The key insight is leveraging the sorted property with two pointers. Start from both ends and move pointers based on sum comparison. Two pointers approach is optimal: Time O(n), Space O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map	O(n)	O(n)	Store seen numbers and their indices in a hash map
Two Pointers	O(n)	O(1)	Use two pointers from start and end, move based on sum comparison
Brute Force	O(n²)	O(1)	Check all possible pairs of numbers

Hash Map — Algorithm Steps

Create hash map to store number -> index mapping
For each number, calculate complement (target - number)
If complement exists in map, return both indices (1-indexed)
Otherwise, add current number and index to map

Visualization

Tap to expand

Step-by-Step Walkthrough

Check

Look for complement in hash map

Store

Add current number to hash map

Found

Return indices when complement found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_SIZE 10007

typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

Node* hashTable[HASH_SIZE];

int hash(int key) {
    return abs(key) % HASH_SIZE;
}

void insert(int key, int value) {
    int index = hash(key);
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

int search(int key) {
    int index = hash(key);
    Node* current = hashTable[index];
    while (current != NULL) {
        if (current->key == key) {
            return current->value;
        }
        current = current->next;
    }
    return -1;
}

int* solution(int* numbers, int numbersSize, int target, int* returnSize) {
    memset(hashTable, 0, sizeof(hashTable));
    
    for (int i = 0; i < numbersSize; i++) {
        int complement = target - numbers[i];
        int idx = search(complement);
        if (idx != -1) {
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = idx + 1;  // Convert to 1-indexed
            result[1] = i + 1;
            *returnSize = 2;
            return result;
        }
        insert(numbers[i], i);
    }
    *returnSize = 0;
    return NULL;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int numbers[1000];
    int numbersSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        numbers[numbersSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int target;
    scanf("%d", &target);
    
    int returnSize;
    int* result = solution(numbers, numbersSize, target, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array with O(1) hash map operations

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n number-index pairs

⚡ Linearithmic Space

185.0K Views

High Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler