Knowledge Guide
Home › DSA

Arrays

Step 2 in the DSA path · 4 concepts · 11 problems

0 / 15 complete

📘 Learn Arrays from zero

The Arrays pattern at its core is the single linear pass: walk the array left to right while carrying a small piece of running state (a min-so-far, a running sum, a best-so-far), updating the answer in O(1) per element. This turns brute-force O(n^2) double loops into one O(n) sweep with O(1) extra space. Reach for it whenever the question is "find the best/total/difference over the array" and each element's contribution can be decided knowing only what came before it — that left-to-right dependency is the trigger. Canonical example: Best Time to Buy and Sell Stock, prices = [7,1,5,3,6,4], find the max profit from one buy then a later sell.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Set up running state
index :  0   1   2   3   4   5
price : [7,  1,  5,  3,  6,  4]
          ^
          i

min_so_far = +inf   best_profit = 0

We do one left-to-right scan. min_so_far = cheapest buy price seen so far, best_profit = best sell-minus-buy found so far.

Both start neutral so the very first element can only improve them, never corrupt the answer.

Step 2 — i=0, price 7 (first buy candidate)
price : [7,  1,  5,  3,  6,  4]
          ^
          i=0

7 < +inf  ->  min_so_far = 7
best_profit = 0  (unchanged)

Since 7 < min_so_far, we take the update-minimum branch: day 0 becomes our cheapest buy.

We do not compute a profit on a day that sets a new minimum — there is no cheaper earlier buy to sell against — which is exactly why min and profit live in separate branches.

Step 3 — i=1, price 1 (new minimum)
price : [7,  1,  5,  3,  6,  4]
              ^
              i=1

1 < 7   ->  min_so_far = 1
best_profit = 0

A cheaper buy appears, so min_so_far drops to 1.

It is safe to overwrite the old min: any future sell prefers the lowest buy seen, and that buy (index 1) is to the left of every day still ahead of us, so order is respected.

Step 4 — i=2, price 5 (first real profit)
price : [7,  1,  5,  3,  6,  4]
                  ^
                  i=2

5 > min_so_far(1)
profit = 5 - 1 = 4  >  best_profit(0)
best_profit = 4     min_so_far = 1

Now price > min_so_far, so we try selling: 5 - 1 = 4 beats 0, so best_profit = 4.

Safe because min_so_far(1) is from an earlier day, so buy-then-sell ordering holds.

Step 5 — i=3, price 3 (no improvement)
price : [7,  1,  5,  3,  6,  4]
                      ^
                      i=3

3 > min_so_far(1)
profit = 3 - 1 = 2  <  best_profit(4)
best_profit = 4   (unchanged)   min_so_far = 1

Selling at 3 gives only 3 - 1 = 2, which does not beat 4, so nothing changes.

We never lower best_profit — it is a running maximum, so a worse day simply gets skipped.

Step 6 — i=4, price 6 (best answer found)
price : [7,  1,  5,  3,  6,  4]
                          ^
                          i=4

6 > min_so_far(1)
profit = 6 - 1 = 5  >  best_profit(4)
best_profit = 5     min_so_far = 1

Day 4 is the peak after the valley: 6 - 1 = 5 beats 4, so best_profit = 5.

This is the optimal trade (buy day 1, sell day 4) and the scan found it without ever looking back.

Step 7 — i=5, price 4 (confirm, finish)
price : [7,  1,  5,  3,  6,  4]
                              ^
                              i=5

4 > min_so_far(1)
profit = 4 - 1 = 3  <  best_profit(5)
best_profit = 5  (final)   min_so_far = 1

Return 5

The last day yields 4 - 1 = 3, no improvement, so the loop ends with best_profit = 5.

One pass, O(n) time and O(1) space — the defining shape of the Arrays running-state pattern.

🎯 Guided practice

  1. Easy — Find the Highest Altitude. A biker starts at altitude 0. gain = [-5, 1, 5, 0, -7] gives the net change between consecutive points; return the highest altitude reached.
    Think: altitude at any point is the running sum of gains so far — the exact pattern from the intro. Carry one variable alt (current altitude) and one best (max seen, starting at 0 because the start counts).
    Trace: start alt=0, best=0. Add −5 → alt=−5, best stays 0. Add 1 → alt=−4, best 0. Add 5 → alt=1, best=1. Add 0 → alt=1, best 1. Add −7 → alt=−6, best 1. Answer: 1.
    Lesson: "running value + track the extreme in the same pass" is one loop, O(n) time, O(1) space — never build a separate prefix array if you only need the max.
  2. Medium — Best Time to Buy and Sell Stock. prices = [7, 1, 5, 3, 6, 4] (indices 0..5); buy on one day, sell on a strictly later day, maximize profit (0 if none).
    Think: naive is every (buy, sell) pair — O(n²). The insight: to sell at index i for max profit, you want the cheapest price at any index before i. So carry minSoFar (lowest buy price up to now) and maxProfit; at each day, candidate profit = price − minSoFar, then update both. This is the "min so far while scanning" trigger.
    Trace (start minSoFar=7, profit=0): index 1 price 1 → 1−7<0, profit 0, minSoFar→1. index 2 price 5 → 5−1=4, profit=4. index 3 price 3 → 3−1=2, profit stays 4. index 4 price 6 → 6−1=5, profit=5. index 5 price 4 → 4−1=3, profit stays 5. Answer: 5 (buy at 1, sell at 6).
    Lesson: collapsing an O(n²) pair search into O(n) by remembering the best "earlier" value is the core array optimization — the same shape recurs in Left/Right Sum Differences and Kids With Greatest Candies (precompute the global max once, then one comparison pass).

✨ Added by the guide — work these before the full problem set.

Lessons in this topic