LeetCode for Environmental Engineers
Problem 1 • Two Sum • Level: Easy
Arrays & Strings | Topic: Hash Map | Phase 1 – Foundation
1. Real-World Context
Imagine you are a field engineer monitoring Biochemical Oxygen Demand (BOD) readings
from sensors placed along a polluted river. Each sensor reports a BOD value in mg/L. Your
water treatment team has defined a critical combined threshold — for example, 9 mg/L —
that, when matched by any two sensors together, triggers an immediate intervention alert.
Mission: Given a list of BOD sensor readings and a target threshold, find the indices of the
two sensors whose readings sum to that threshold.
Example:
readings = [2, 7, 11, 15] target = 9
Sensor 0 reads 2 mg/L + Sensor 1 reads 7 mg/L = 9 ✅
2. Learning Objective
Understand the brute-force (O(n²)) approach and its limitations.
Learn the hash-map technique to solve Two Sum in O(n) time.
Trace through the algorithm step by step using a real river data example.
Recognise the 'complement lookup' pattern that recurs across dozens of problems.
3. Approach 1 — Brute Force (Slow)
Check every possible pair of sensors. For each sensor i, compare it with every sensor j
(where j > i) and test whether readings[i] + readings[j] == target.
Time complexity: O(n²) — doubles with every additional sensor.
Space complexity: O(1) — no extra memory used.
Why this is bad for large river networks:
With 1,000 sensors you make ~500,000 comparisons. With 10,000 sensors that becomes
~50,000,000 comparisons. Real-time flood or pollution alerts cannot afford this delay.
def twoSum_brute(readings, target):
for i in range(len(readings)):
for j in range(i+1, len(readings)):
if readings[i] + readings[j] == target:
return [i, j]
4. Approach 2 — Hash Map (Fast, Optimal)
Think of carrying a field notebook as you walk along the river. At each sensor you ask:
'What reading do I need to pair with this one to hit the target?' You check your notebook. If
it's already recorded — you've found your pair. If not, you write the current reading into
the notebook and move on.
Time complexity: O(n) — each sensor is visited exactly once.
Space complexity: O(n) — the notebook stores at most n entries.
def twoSum(readings, target):
notebook = {} # {reading_value: sensor_index}
for i, reading in enumerate(readings):
need = target - reading # what complement do I need?
if need in notebook: # already seen it?
return [notebook[need], i]
notebook[reading] = i # record this reading
return [] # no solution found
5. Step-by-Step Trace
Input: readings = [3, 5, 1, 8, 2] target = 10
Step Sensor (i) Reading Need (10 – In Notebook? Notebook state
reading)
1 0 3 mg/L 7 No {3: 0}
2 1 5 mg/L 5 No {3:0, 5:1}
3 2 1 mg/L 9 No {3:0, 5:1, 1:2}
4 3 8 mg/L 2 No {3:0, 5:1, 1:2, 8:3}
5✅ 4 2 mg/L 8 YES! → index Return [3, 4]
3
Answer: Sensors at index 3 (reading=8 mg/L) and index 4 (reading=2 mg/L) sum to 10
mg/L. Combined zone flagged for treatment! 🌊
6. Key Insight
• Complement thinking: Instead of asking 'do these two add up?', ask 'what do I still
need?' This flips an O(n²) comparison into an O(1) lookup.
• One pass: You only walk the river once. The notebook grows as you go — no
backtracking.
• Order matters for the notebook: At step 4 (reading=8, need=2), the value 2 hadn't been
recorded yet. The notebook only knows the past, not the future. That's why we check first,
then record.
• Pattern reuse: This exact 'check complement in hashmap' pattern appears in Two Sum
II, 3Sum, Subarray Sum Equals K, and many more problems.
7. Complexity Summary
Approach Time Space
Brute Force O(n²) O(1)
Hash Map (optimal) O(n) O(n)
8. Practice Exercises
Difficulty Input Expected Output
Easy readings = [2, 7, 11, 15], target = [0, 1]
9
Easy readings = [3, 2, 4], target = 6 [1, 2]
Medium readings = [3, 5, 1, 8, 2], target = [3, 4]
10
Medium readings = [0, 4, 3, 0], target = 0 [0, 3]
Hard What if multiple pairs exist? How Extend with a list
would you return all of them?
9. NotebookLM Discussion Prompts
Use these prompts to generate your NotebookLM audio overview:
1. Explain the Two Sum problem using the river sensor analogy and walk through the
hash map solution step by step.
2. Why is the brute-force O(n²) approach a problem for real-time environmental
monitoring systems?
3. What is 'complement thinking' and how does it change our approach to array search
problems?
4. How does the field notebook (hash map) remember past sensor readings, and why does
the order of check-then-record matter?
5. What other environmental engineering problems could be modelled as a Two Sum
variant?
6. Compare the time and space complexity of the two approaches and explain the trade-
off.
LeetCode Study Plan • Arrays & Strings • Problem 1 of 77 • Next: Best Time to Buy and Sell Stock