HashMap can reduce nested loop problems from O(n²) to O(n).
Problem stats
Before
Use two nested loops and check every pair of numbers. Return the indices when their sum equals the target.
After
Store previously visited numbers inside a HashMap. For every number check if target-currentNumber already exists.
The optimized implementation, ready for interview preparation and quick revision.
Solution.java
1import java.util.HashMap;2import java.util.Map;3 4public class Solution {5 6 public int[] twoSum(int[] nums, int target) {7 8 Map<Integer, Integer> map = new HashMap<>();9 10 for (int i = 0; i < nums.length; i++) {11 12 int complement = target - nums[i];13 14 if (map.containsKey(complement)) {15 return new int[] { map.get(complement), i };16 }17 18 map.put(nums[i], i);19 }20 21 return new int[] {};22 }23 24 public static void main(String[] args) {25 26 Solution solution = new Solution();27 28 int[] nums = {2, 7, 11, 15};29 int target = 9;30 31 int[] result = solution.twoSum(nums, target);32 33 System.out.println("[" + result[0] + ", " + result[1] + "]");34 }35}Analyze the efficiency of the algorithm by understanding its time and space complexity across different execution scenarios.
Time complexity
Space complexity
By execution case
Best case
O(n)
Average case
O(n)
Worst case
O(n)
This solution achieves a O(n) time complexity while using O(n) extra memory. It is considered the optimal approach for this problem and is suitable for coding interviews as well as competitive programming.
Every coding problem teaches a pattern. Focus on the concepts, avoid common mistakes, and remember the interview-worthy takeaways instead of memorizing code.
The biggest takeaway from this problem.
HashMap can reduce nested loop problems from O(n²) to O(n).
Explain why the optimized solution works before writing the final code. Interviewers care about your thinking process as much as your implementation.
Avoid jumping directly to coding. Always analyze edge cases, constraints, and the optimal approach before implementation.
Focus on understanding the algorithm's pattern instead of memorizing the code. Once the logic becomes clear, implementing the solution in any programming language becomes much easier.
Every DSA problem introduces a reusable pattern. Instead of remembering the exact solution, remember the thought process that led to it. Over time, these patterns will help you solve new problems much faster and perform better in coding interviews.
Practice consistently and move through the roadmap one problem at a time.
Practice similar problems to strengthen your understanding of the underlying algorithm and improve pattern recognition.