Scale Engineer

Two Sum

Easy
#0001Time: O(n²)Space: O(1)114 companies
Data structures
ArrayHash Table
Companies
AMDAccentureAccoliteAdobe

Prompt

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

 

Constraints:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

 

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to check every possible pair of numbers in the array. We can use two nested loops to iterate through all pairs and see if their sum equals the target.

Algorithm

  • Iterate through the array with an index i from 0 to n-2.
  • For each i, iterate through the rest of the array with an index j from i+1 to n-1.
  • Check if nums[i] + nums[j] == target.
  • If the condition is true, return [i, j].

Walkthrough

We use two nested loops to find the pair of numbers. The outer loop, with index i, iterates from the beginning of the array to the end. The inner loop, with index j, starts from i + 1 to avoid using the same element twice and to avoid duplicate pairs. Inside the inner loop, we check if nums[i] + nums[j] is equal to the target. If the sum is equal to the target, we have found our solution and can return the indices [i, j]. Since the problem guarantees exactly one solution, we don't need to worry about finding multiple pairs or no pairs at all.

class Solution {    public int[] twoSum(int[] nums, int target) {        int n = nums.length;        for (int i = 0; i < n - 1; i++) {            for (int j = i + 1; j < n; j++) {                if (nums[i] + nums[j] == target) {                    return new int[]{i, j};                }            }        }        return new int[]{}; // Should not be reached as per problem statement    }}

Complexity

Time

O(n²)

Space

O(1)

Trade-offs

Pros

  • Simple to understand and implement.

  • Uses constant extra space.

Cons

  • Inefficient for large input arrays due to its quadratic time complexity.

Solutions

public class Solution {    public int[] TwoSum(int[] nums, int target) {        var m = new Dictionary < int,            int > ();        for (int i = 0, j;; ++i) {            int x = nums[i];            int y = target - x;            if (m.TryGetValue(y, out j)) {                return new [] {                    j,                    i                };            }            if (!m.ContainsKey(x)) {                m.Add(x, i);            }        }    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

Next →

Next problem