What is the time complexity of Two Sum II - Input Array Is Sorted?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Two Sum II - Input Array Is Sorted?

This problem uses Array, Two Pointers, Binary Search. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Two Sum II - Input Array Is Sorted?

Insight 1: The array being sorted allows us to use the Two Pointers technique or Binary Search for an efficient solution. Insight 2: The Two Pointers approach is particularly well-suited for this problem due to its O(1) space complexity.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Two Sum II - Input Array Is Sorted - LeetCode 167 Solution

Q: How to solve Two Sum II - Input Array Is Sorted?

The provided solution employs the Two Pointers technique. We initialize two pointers, `left` and `right`, to the beginning and end of the array, respectively. We then iterate through the array, adjusting the pointers based on the sum of the elements they point to. If the sum is less than the target, we move the `left` pointer to the right, increasing the sum. If the sum is greater than the target, we move the `right` pointer to the left, decreasing the sum. When the sum equals the target, we have found the two numbers, and we return their 1-based indices.

Q: Which companies ask LeetCode 167. Two Sum II - Input Array Is Sorted in interviews?

This problem is frequently asked at EPAM Systems, Infosys, J.P. Morgan, Oracle, Qualcomm and 3 more companies.

Two Sum II - Input Array Is Sorted - Complete Solution Guide

Two Sum II - Input Array Is Sorted is LeetCode problem 167, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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. Let these two numbers be numbers[index 1 ] and numbers[index 2 ] where 1 <= index 1 < index 2 <= numbers.length . Return the indices of the two numbers, index 1 and index 2 , added by one as an integer array [index 1 , index 2 ] of length 2. The tests are generated such that there is exactly one solution . You may not use the same elemen

Detailed Explanation

The problem 'Two Sum II - Input Array Is Sorted' requires us to find two numbers within a sorted array that add up to a given target value. We must return the 1-based indices of these two numbers. The array is guaranteed to have exactly one solution, and we cannot use the same element twice. Crucially, we are given that the input array `numbers` is already sorted in non-decreasing order. The problem emphasizes the need for a solution with constant extra space.

Solution Approach

The provided solution employs the Two Pointers technique. We initialize two pointers, `left` and `right`, to the beginning and end of the array, respectively. We then iterate through the array, adjusting the pointers based on the sum of the elements they point to. If the sum is less than the target, we move the `left` pointer to the right, increasing the sum. If the sum is greater than the target, we move the `right` pointer to the left, decreasing the sum. When the sum equals the target, we have found the two numbers, and we return their 1-based indices.

Step-by-Step Algorithm

Step 1: Initialize two pointers, `left` to 0 and `right` to `len(numbers) - 1`.
Step 2: While `left` is less than `right`, calculate the sum of `numbers[left]` and `numbers[right]`.
Step 3: If the `current_sum` is equal to the `target`, return `[left + 1, right + 1]` (adding 1 to convert to 1-based indices).
Step 4: If the `current_sum` is less than the `target`, increment `left` by 1 to increase the sum.
Step 5: If the `current_sum` is greater than the `target`, decrement `right` by 1 to decrease the sum.
Step 6: If no solution is found within the while loop (which shouldn't happen given the problem constraints), return an empty array or null (depending on the language).

Key Insights

Insight 1: The array being sorted allows us to use the Two Pointers technique or Binary Search for an efficient solution.
Insight 2: The Two Pointers approach is particularly well-suited for this problem due to its O(1) space complexity.
Insight 3: Since we need to return 1-based indices, we have to increment the 0-based indices obtained from the algorithm.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers, Binary Search.

Companies

Asked at: EPAM Systems, Infosys, J.P. Morgan, Oracle, Qualcomm, Yandex, Zomato, eBay.

Two Sum II - Input Array Is Sorted | LeetCode 167

Medium

Array Two Pointers Binary Search

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int current_sum = numbers[left] + numbers[right];

            if (current_sum == target) {
                return new int[] {left + 1, right + 1};
            } else if (current_sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[] {};
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 167: Two Sum II - Input Array Is Sorted - Detailed explanation and solution approaches.

Topics

Array Two Pointers Binary Search

Companies

EPAM SystemsInfosysJ.P. MorganOracleQualcommYandexZomatoeBay

Stats

Difficulty:Medium

Languages:4

Companies:8

Problem #:167

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize two pointers, `left` to 0 and `right` to `len(numbers) - 1`.
2
Step 2: While `left` is less than `right`, calculate the sum of `numbers[left]` and `numbers[right]`.
3
Step 3: If the `current_sum` is equal to the `target`, return `[left + 1, right + 1]` (adding 1 to convert to 1-based indices).
4
Step 4: If the `current_sum` is less than the `target`, increment `left` by 1 to increase the sum.
5
Step 5: If the `current_sum` is greater than the `target`, decrement `right` by 1 to decrease the sum.
6
Step 6: If no solution is found within the while loop (which shouldn't happen given the problem constraints), return an empty array or null (depending on the language).

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(n) because, in the worst case, the `left` and `right` pointers will traverse the entire array once. The space complexity is O(1) because we only use a constant amount of extra space for the `left` and `right` pointers, regardless of the input size.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Binary Search

For each number in the array, perform a binary search for the complement (target - number).

Time: O(n log n)Space: O(1)

Trade-offs: While conceptually valid, binary search adds a logarithmic factor, resulting in a O(n log n) time complexity, making Two Pointers more efficient. Binary Search can be more appropriate if, in a similar problem, only one element in the array is sorted and the rest of the array elements are unsorted.

Hash Map

Iterate through the array and store each number and its index in a hash map. For each number, check if its complement exists in the hash map.

Time: O(n)Space: O(n)

Trade-offs: Although it offers O(n) time complexity like Two Pointers, it requires O(n) extra space for the hash map. The problem explicitly states that the solution must use constant extra space, making the Hash Map approach unsuitable.

✨

Key Insights

1Insight 1: The array being sorted allows us to use the Two Pointers technique or Binary Search for an efficient solution.
2Insight 2: The Two Pointers approach is particularly well-suited for this problem due to its O(1) space complexity.
3Insight 3: Since we need to return 1-based indices, we have to increment the 0-based indices obtained from the algorithm.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Edge Cases

Edge case 1: Small input array (e.g., length 2). The Two Pointers approach correctly handles this as the pointers start at the beginning and end and converge if the sum matches the target.
Edge case 2: Negative numbers in the input array. The algorithm still works correctly with negative numbers because it adjusts the pointers based on whether the sum is less than or greater than the target.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to add 1 to the indices before returning them. The problem specifically requires 1-based indices.

✗Common mistake 2: Not handling the case where no solution is found. Although the problem states there's always a solution, it's good practice to consider this scenario in other contexts (or edge cases not described).

✗Common mistake 3: Using the same element twice. The problem specifies that the same element cannot be used twice. Two Pointers inherently avoids this because `left` and `right` must be distinct.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Finding pairs of transactions in a sorted log file that sum to a specific amount (e.g., for reconciliation purposes).

🏦Real-world scenario 2: Identifying two stocks from a sorted list whose prices add up to a target investment value for portfolio balancing.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 15, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Two Sum II - Input Array Is Sorted"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?