Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 33

Solving Two Sum: An Algorithmic Analysis

Recommended resources

Welcome back! In our last lesson, we saw how a HashMap can be used to efficiently solve frequency-counting problems. We're about to see just how versatile that tool is as we tackle one of the most iconic problems in all of software engineering interviews: the "Two Sum" problem.

This lesson will guide you through solving this classic challenge, which is LeetCode's problem #1 and a staple of technical interviews. We will start with a straightforward brute-force solution, analyze why it's not optimal, and then apply our HashMap knowledge to develop a highly efficient solution. By the end, you'll not only have the code but also a deep understanding of the time-space complexity trade-offs and how to present this problem in an interview setting, aligning perfectly with your goal of becoming job-ready.

1. Understanding the "Two Sum" Problem

The problem is simple to state but offers a great opportunity to demonstrate your problem-solving skills. Let's get the formal definition.

Solving LeetCode's Two Sum in Java

This article from Medium provides a clear and concise introduction to the problem.

Please read the "Introduction" section. Focus on the formal problem statement and review the three examples provided. This will give you a solid grasp of the input (nums array, target integer) and the expected output (an array of two indices).

To summarize, your task is to find two numbers in an array that add up to a specific target and return their indices.

2. The Brute-Force Approach: A First Attempt

When faced with a new problem, it's often best to start with the most intuitive solution, even if it's not the most efficient. For "Two Sum," this means checking every possible pair of numbers in the array.

The logic is as follows:

  1. Take the first number.
  2. Add it to every other number in the array, one by one.
  3. If a pair sums to the target, we're done! Return their indices.
  4. If not, move to the second number and repeat the process, adding it to every subsequent number.
  5. Continue until a pair is found.

This involves using two nested loops. The outer loop picks an element, and the inner loop iterates through the remaining elements to find a match.

2 Sum Problem | 2 types of the same problem for Interviews | Brute-Better-Optimal

The "take U forward" channel provides an excellent explanation of this initial thought process.

Watch the segment on the brute-force method from this part of the video. The presenter visualizes the nested loop logic and discusses why its time complexity is O(n^2).

Now, let's look at the implementation in Java and a more formal complexity analysis.

Two Sum LeetCode 1 Solution: Brute Force, Two Pointers ...

This comprehensive guide provides a clean Java implementation of the brute-force method.

In the article, find the "Java — Brute Force" section and study the Java code. Notice how the inner loop starts from j = i + 1 to avoid using the same element twice and to avoid re-checking pairs. Then, scroll down to the "Time & Space Complexity" section and read the analysis for the brute-force approach. This confirms its time complexity is O(n^2) and its space complexity is O(1).

The brute-force solution is correct, but its time complexity makes it very slow for large arrays. If an array has 10,000 elements, this approach would require roughly 100,000,000 operations. We can do much better.

This graph illustrates how different time complexities scale with input size. The `O(n²)` curve (Quadratic Time) grows significantly faster than the `O(n)` curve (Linear Time), highlighting why the brute-force approach is inefficient for larger inputs.

3. The Optimal Solution: Leveraging a HashMap

How can we avoid the nested loop? The bottleneck is the inner loop, which performs a linear search for the second number. If only there were a way to find that second number in constant time...

This is exactly what we learned in the last lesson. A HashMap provides, on average, an time complexity for lookups (get or containsKey). Since you're familiar with Python, this is analogous to the performance of a dict.

The core idea is this: As we iterate through the array, for each element x, we can calculate the number we need to find, which we'll call the complement. The complement is simply target - x. We then need to check if this complement exists in the part of the array we have already seen.

The one-pass HashMap algorithm works like this:

  1. Create an empty HashMap to store number -> index pairs.
  2. Iterate through the nums array from left to right.
  3. For each element nums[i]:
    a. Calculate the complement: complement = target - nums[i].
    b. Check if the complement exists as a key in your HashMap. If it does, you've found the solution! The indices are the one stored in the map for the complement, and the current index i.
    c. If the complement is not in the map, add the current number nums[i] and its index i to the map.
  4. By checking for the complement before adding the current element, we cleverly handle cases with duplicates (like [3, 3] with target = 6) and avoid matching an element with itself.
This pair of charts visually contrasts the two approaches. The 'Brute Force' method involves checking pairs sequentially, whereas the 'Optimized (Hash Map)' approach allows us to find the required complement almost instantly.

Let's watch a detailed walkthrough of this superior approach.

2 Sum Problem | 2 types of the same problem for Interviews | Brute-Better-Optimal

This segment from the "take U forward" video masterfully explains the intuition and execution of the HashMap solution.

Watch from Better Solution using Hashing. The presenter develops the thought process, performs a dry run by building the map step-by-step, and implements the code. This is a crucial segment for understanding the logic.

With the intuition clear, let's examine a polished Java implementation and its complexity.

Two Sum LeetCode 1 Solution: Brute Force, Two Pointers ...

This resource provides the standard, interview-ready one-pass HashMap solution.

First, find the section titled "Java — Optimized Fixed Sliding Window" (this is a minor misnomer in the article; it is the correct HashMap solution). Study the optimized Java code. Next, for a key insight, scroll down to the "One-pass Hash Map" section within the JavaScript examples. The logic is language-agnostic. Read the explanation on why you should check for the complement before inserting the current element. Finally, in the "Time & Space Complexity" section, review the analysis under the "3. One-pass hash map — optimal" heading, located in this paragraph. This confirms the Time Complexity is O(N) and Space Complexity is O(N).

This solution involves a trade-off: we use extra space for the HashMap ( space) to reduce the time complexity from to . In almost all interview scenarios, this is the preferred and expected optimal solution.

4. Presenting Your Solution in an Interview

For your goal of landing a software engineering role, knowing the solution is only half the battle. You also need to communicate it effectively. The "Two Sum" problem is a great chance to demonstrate a structured thought process.

A great strategy is:

  1. Clarify requirements (ask about duplicates, sorted arrays, etc.).
  2. Start by explaining the brute-force solution and its complexity. This shows you can find a working solution first.
  3. Discuss the bottleneck ( time) and propose an optimization using a HashMap.
  4. Explain the one-pass algorithm, its time-space trade-off, and walk through an example.

This following resource is invaluable for learning how to frame your answer.

Two Sum LeetCode 1 Solution: Brute Force, Two Pointers ...

This part of the article is specifically designed to get you interview-ready.

Start by reading the short answer template for a concise summary of what to say. Then, review the interview script to see how to structure your complete explanation. Finally, study the interview FAQs to prepare for common follow-up questions an interviewer might ask.

Conclusion

Today, you've not only solved a fundamental coding problem but also learned how to approach it like a professional software engineer. You've progressed from a simple but inefficient solution to a highly optimized one, analyzing the trade-offs along the way.

Here are your key takeaways:

  • The Two Sum Problem: Given an array and a target, find the indices of two numbers that sum to the target.
  • Brute-Force Solution: Uses nested loops, resulting in time and space complexity. It's correct but slow.
  • Optimized HashMap Solution: Uses a single pass and a HashMap to achieve time and space complexity. This is the standard optimal answer.
  • The Core Trade-off: We sacrifice space to gain a significant improvement in time, a common theme in algorithm design.
  • Interview Strategy: Articulating your thought process, from brute-force to optimal, is a key skill.

In our next lesson, we will shift gears from arrays and hash-based structures to a completely new type of data structure: the linked list. You will learn how to implement a singly linked list from scratch, which is another foundational skill for any aspiring software engineer.