Why O(n²) Destroys Production Systems (LeetCode #1 Two Sum)

Added: 2026-06-03

[00:00:00]Most people treat to some as a warm-up. I want  to show you why it's actually everywhere in production software and why the approach you  pick matters. Uh let's you open Google Maps and you type your destination in milliseconds.  It find two road segments that add up to your total travel distance. That lookup it's  two sum. Let's break it down completely.

[00:00:25]If you look at the map, suppose segment A is  2 miles and segment B is 7 miles. Together, we get our total destination distance of 9  mi. All right, the problem. Given an array of integers and a target number, return the indices  of two numbers that add up to the target. Let me write this on the notebook so we can see it  clearly. Here is our array 2 7 11 15 and the indices are 0 1 2 3 and target is 9. So we need  to find which two numbers in this array add up to 9. Uh look at index zero the number is 2 and  if you look at one the number is 7. So 2 + 7 = 9.

[00:01:25]That's our answer. So we written 0 and 1. It's  simple to understand. Now let's talk about how to find it because this is where it's gets  interesting. The first instinct most people have is check every pair. Pick the first number.  Check it against every other number. If they add up to the target, done. If not, move to the next  number. Let me draw this. I'm at index zero.

[00:01:53]That's the number is 2. Now my inner loop checks 2  + 7= 9. We found it. But what if they don't match?

[00:02:02]I will check 2 + 11 equal to 13. No match. And 2  + 15. No. And then I'll move to index one. And I will check for 7 + 11. 7 + 11 is And 7 + 15 and so  on. This is called brute force. Two nested loops.

[00:02:32]Here is the code. In line one, outer loop, we  pick every element as a candidate. And line two, inner loop start at i + 1. We never  check a pair twice. In line three, the actual check uh do they add up to the  target? We will check that. And line four, if we return the two indices immediately. The  time complexity for this is big of n² because of two nested loops. And the space complexity  is big of one because no extra memory is used.

[00:03:09]Now, here's where this matters in the real  world. Imagine you are a junior developer at an e-commerce company. Your product catalog has  1 million items. A customer wants two items that together cost exactly $50. With brute force, you  are checking every pair. 1 million items means 50 billion comparisons. Your server doesn't just slow  down. Your server catches fire. In bioinformatics, researchers actually use brute force on toy data  sets. But production genomic systems never. The point is this. Brute force works on lead code  examples. It fails in production. We need smarter approach. Here is the key insight that  changes everything. For every number I look at, I don't need to check every other number. I just  need to remember what I have already seen. Here is how I think about. If my target is 9 and I  am looking at number two, I don't need to scan whole array. I just ask, have I seen seven before?  Because 9 - 2 is 7. That's the complement. Create an empty hashmap. Think of it as a table. Two  columns like value and index. And in step one, I'm at index zero. So the complement is 9 - 2  that is 7. So uh we'll be checking does seven in our map or not. The map is empty. So we store  uh two and zero in the hashmap. Now we'll move to step two that is index one and we'll check  complement that is 9 - 7 equal to 2 and we'll check check in our app uh the value to exist. So  we'll be written 01 as our answer. I only looped once one pass through the array. This is where  hashmap exists. big of one lookup. It's not big of n and not big of n square. It's a constant  time. Here is the code. In line one, we seen is our hashmap. It maps a value to its index. In line  two, we loop through the array using enumerate.

[00:05:46]This gives us both the index i and the number  name at the same time. In line three, we complete compute the complement the number that we need.  In line four, we check the map. This is zero of one instant. If complement is already in scene,  we found our pair. In line five, we return both indices. Scene complement is the earlier index  and i is the current. If not founded, we store the current number and index in the map. So, a future  number can find it. The time complexity is big of n one pass and the space complexity is big of  pen. The hashmap can hold up to n elements. This is our best solution. This is what uh you should  write in interviews. This is what production code looks like. This exact pattern I need x I have  seen it before is everywhere in real systems.

[00:06:48]First, Google Maps routing. For each road segment,  the system looks up the complement distance in a hashmap finds optimal pairs in big off and not  big of and square. In stripe, the speed pay means uh given a total charge amount. Find two line  items that sum to it. Big off and hashmap lookup per transaction millions of times a day. and uh  React cons reconciler. When React compare your old and new virtual DOM, it maps node keys to  positions using a hashmap. We go of one lookup to find matching nodes. That's why React is fast.  And in elastic search, the inverted index which powers every search you ever done is a hashmap.  What maps to document ids to sum is a primitive hiding inside full text search. The next time you  search something on Google, you are running to sum just with better hardware. Let me put them side  by side one more time. Brute force big of n square time big of one space. It's not production ready.  Hashmap uh is big of n time and big of n space.

[00:08:06]It's a best solution. Both have early exit. We  return the moment we find the answer. Hashmap is more readable once you understand the pattern  and it scales to billions of record. So what did we cover today? We started with the institution  Google maps real systems. We built proof force, understand it, cod it and dry ran it. We  understood why it fails at school scale.

[00:08:32]Then we built the hashmap solution. one bus we  go of end time and we dry ran it step by step on the notebook and we connected it back to Google  maps stripe react and elastic search for interview uh answer is hashmap and big of end time and big  of end space and uh what if a senior engineer asks uh if you have a billion elements and can't  fit the hashmap in memory that's your next problem to think about I will answer that in  future video This is Shria Explains where we break down complex coding concepts into simple  real world learning. Hit the subscribe button so you don't miss the next breakdown. I'm  Sri Teja and I'll see you in the next one.