167. Two Sum II - Input Array Is Sorted - Detailed Explanation

Free Coding Questions Catalog
Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
Given a 1-indexed array of integers numbers that is sorted in non-decreasing order and a target integer target, find two numbers such that they add up to target. Return the indices of the two numbers as an array [index1, index2] where 1 <= index1 < index2 <= numbers.length. You are guaranteed that there is exactly one solution, and you may not use the same element twice.

Examples:

  • Example 1:

    • Input: numbers = [2,7,11,15], target = 9
    • Output: [1,2]
    • Explanation:
      The numbers at indices 1 and 2 (1-indexed) are 2 and 7 respectively. Their sum is 9.
  • Example 2:

    • Input: numbers = [2,3,4], target = 6
    • Output: [1,3]
    • Explanation:
      The numbers at indices 1 and 3 are 2 and 4, which add up to 6.
  • Example 3:

    • Input: numbers = [-1,0], target = -1
    • Output: [1,2]
    • Explanation:
      The numbers at indices 1 and 2 are -1 and 0, and their sum is -1.

Constraints:

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • There is exactly one solution.

Hints

  • Hint 1: Since the array is sorted, think about using two pointers – one starting at the beginning and the other at the end of the array.
  • Hint 2: Use the fact that if the sum of the two pointers is too high, you can move the right pointer to the left; if the sum is too low, move the left pointer to the right.

Approaches

Brute Force Approach

Idea:

  • Check every pair of numbers (using nested loops) to see if they add up to the target.
  • Return the pair of indices when found.

Drawbacks:

  • Time Complexity: O(n²) – inefficient for large arrays.
  • Not ideal since the array is already sorted, which hints at a better approach.

Optimal Approach – Two Pointers

Idea:

  • Use two pointers:
    • Left Pointer: Starts at the beginning of the array.
    • Right Pointer: Starts at the end of the array.
  • Compute the sum of the elements at these pointers.
    • If the sum equals the target: Return the 1-indexed positions.
    • If the sum is less than the target: Increase the left pointer to increase the sum.
    • If the sum is greater than the target: Decrease the right pointer to decrease the sum.

Step-by-Step Walkthrough:

Consider the array [2,7,11,15] with target = 9:

  1. Initialization:
    • left = 0 (points to 2)
    • right = 3 (points to 15)
  2. First Iteration:
    • Sum = 2 + 15 = 17 which is greater than 9.
    • Move right pointer left to index 2.
  3. Second Iteration:
    • left = 0 (still 2), right = 2 (points to 11).
    • Sum = 2 + 11 = 13 still greater than 9.
    • Move right pointer left to index 1.
  4. Third Iteration:
    • left = 0 (points to 2), right = 1 (points to 7).
    • Sum = 2 + 7 = 9 equals the target.
    • Return indices [0 + 1, 1 + 1] = [1,2].

Complexity Analysis:

  • Time Complexity: O(n) – each element is visited at most once.
  • Space Complexity: O(1) – constant extra space is used.

Code Implementations

Python Code (Two Pointers Approach)

Python3
Python3

. . . .

Java Code (Two Pointers Approach)

Java
Java

. . . .

Step-by-Step Walkthrough and Visual Example

Let's walk through the example numbers = [2,7,11,15] and target = 9:

  1. Initialize:

    • left = 0 (points to 2)
    • right = 3 (points to 15)
  2. Iteration 1:

    • Calculate current_sum = 2 + 15 = 17
    • Since 17 > 9, move the right pointer leftwards:
      • Now, right = 2 (points to 11)
  3. Iteration 2:

    • With left = 0 (points to 2) and right = 2 (points to 11):
    • Calculate current_sum = 2 + 11 = 13
    • Since 13 > 9, move the right pointer leftwards:
      • Now, right = 1 (points to 7)
  4. Iteration 3:

    • With left = 0 (points to 2) and right = 1 (points to 7):
    • Calculate current_sum = 2 + 7 = 9
    • current_sum equals target. Return the answer as [left + 1, right + 1] = [1, 2].

Common Mistakes

  • Not Returning 1-Indexed Positions:
    Since the array is 1-indexed according to the problem, remember to add 1 to each index before returning.

  • Using Nested Loops Unnecessarily:
    The two pointers approach takes advantage of the sorted property of the array and is far more efficient than a brute force nested loops solution.

  • Incorrect Pointer Updates:
    Be sure to adjust the pointers correctly based on whether the current sum is less than or greater than the target.

Edge Cases

  • Array with Two Elements:
    With only two elements, the solution is trivial but ensure your code handles this without error.
  • Negative Numbers:
    Even though the array is sorted, it can contain negative numbers. The two pointers approach still applies.
  • Guaranteed One Solution:
    The problem guarantees exactly one solution, so you don’t need to handle cases where no solution exists.

Variations:

  • Two Sum (Unsorted Array):
    In the unsorted version, a hash map is typically used to achieve O(n) time.
  • 3Sum and 4Sum:
    These problems require finding triplets or quadruplets that add up to a target value.
  • Closest Two Sum:
    Find the pair of numbers whose sum is closest to the target value.
TAGS
leetcode
CONTRIBUTOR
Design Gurus Team
-

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
How hard is it to join OpenAI?
How do I prepare for a project management interview?
Is network engineer part of it?
Related Courses
Image
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.
Image
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Image
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
Image
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.
;