1.1 Arrays & Strings — DSA Crash Course

Deep Dive: Why Array Techniques Work

Beginner tip: An array is just a numbered list. arr[0] is the first item, arr[1] is the second, etc. The key superpower of arrays is that jumping to any position is instant (O(1)) because items are stored side by side in memory.

The Two-Sum Insight (HashMap Pattern)

Imagine you have a bag of numbered balls and you need to find two that add up to 9.

Brute force (slow): Pick up each ball and compare it with every other ball. With 1000 balls, that is 500,000 comparisons.

Smart way (HashMap): As you pick up each ball, write its number on a sticky note and pin it to a board. Before picking up the next ball, check the board: "Do I need this number?" This way you look at each ball only once.

Walk through nums = [2, 7, 11, 15], target = 9:

Step 1: Pick up 2. Need 9-2=7. Board is empty.     Pin "2" to board.
Step 2: Pick up 7. Need 9-7=2. Check board: 2 IS there! Done.

Two steps instead of checking all pairs. That is the power of a HashMap.

The Kadane's Insight (Maximum Subarray)

Walk through nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Index:    0    1    2    3    4    5    6    7    8
Value:   -2    1   -3    4   -1    2    1   -5    4
curr:    -2    1   -2    4    3    5    6    1    5
max:     -2    1    1    4    4    5    6    6    6
                         ^--- reset! 4 > (4 + -2) so start fresh here

Key decision at each index: "Is it better to extend my current subarray or start fresh?" If curr + num < num, the accumulated sum is hurting us -- start over.

The Two Pointers Insight (Sorted Arrays)

For 3Sum: sort [-1, 0, 1, 2, -1, -4] -> [-4, -1, -1, 0, 1, 2]

Fix i=1 (val=-1), lo=2, hi=5:
  -1 + -1 + 2 = 0  -> FOUND! Record [-1,-1,2]. Move both pointers.
  -1 + 0 + 1 = 0   -> FOUND! Record [-1,0,1].

Why sorting helps: With sorted data, you know which direction to move. Sum too small? Move left pointer right (bigger number). Sum too big? Move right pointer left (smaller number). This eliminates O(n) possibilities per step instead of checking them all.

The Prefix/Suffix Insight (Product of Array Except Self)

Problem: return an array where out[i] = product of every nums[j] for j != i.

The "obvious" approach is total = product(nums) then out[i] = total / nums[i]. Two reasons we do not do this:

The constraint usually forbids division. That is the whole point of the problem.
Zeros break it. If any nums[i] == 0, total is 0 and we cannot divide back out cleanly. Handling "exactly one zero" vs "two or more zeros" turns into a special-case mess.

The two-pass trick: each out[i] is (product of everything LEFT of i) * (product of everything RIGHT of i). Compute each side separately.

Walk through nums = [1, 2, 3, 4]:

Pass 1 (left -> right): out[i] = product of nums[0..i-1]
  out[0] = 1                     (nothing to the left)
  out[1] = out[0] * nums[0] = 1 * 1 = 1
  out[2] = out[1] * nums[1] = 1 * 2 = 2
  out[3] = out[2] * nums[2] = 2 * 3 = 6
  After pass 1: out = [1, 1, 2, 6]   <-- prefix products

Pass 2 (right -> left): multiply in suffix product on the fly
  suffix = 1
  i=3: out[3] = out[3] * suffix = 6  * 1  =  6   then suffix *= nums[3] -> suffix = 4
  i=2: out[2] = out[2] * suffix = 2  * 4  =  8   then suffix *= nums[2] -> suffix = 12
  i=1: out[1] = out[1] * suffix = 1  * 12 = 12   then suffix *= nums[1] -> suffix = 24
  i=0: out[0] = out[0] * suffix = 1  * 24 = 24   then suffix *= nums[0] -> suffix = 24

Result: out = [24, 12, 8, 6]

Why O(1) extra space (besides the output array): the output itself doubles as the prefix-products buffer in pass 1, then we fold the suffix product into it in pass 2 using a single scalar suffix. No second array needed. Two linear passes, one running variable -- that is the whole trick.

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About Arrays

Why Arrays Exist

Need: Fast access to element by position. How: Contiguous memory -> arr[i] in O(1).

When You See an Array Problem, Ask Yourself

1. Can I SORT it? Sorting unlocks Two Pointers and Binary Search.
2. Can I use EXTRA SPACE (HashMap/Set)? Trading space for time is often the key.
3. Is there a SUBARRAY involved? Think Sliding Window or Prefix Sum.
4. Am I comparing PAIRS? Think Two Pointers (if sorted) or HashMap (if unsorted).
5. Can I process LEFT-TO-RIGHT and build a running answer? Think Kadane's / Greedy.

The 5 Array Patterns to Internalize

Pattern	Signal	Core Idea
HashMap/Set	"Find pair", "check existence"	O(1) lookup trades space for time
Two Pointers	Sorted input, find pair/triplet	Converge from both ends
Prefix/Suffix	"Product except self", "range sum"	Precompute cumulative values
Kadane's	"Maximum subarray"	Running max, reset when negative
Index as Hash	"First missing positive", range [1,n]	Use array indices as storage

String-Specific Thinking

Strings are just character arrays. Most array techniques apply.
Immutability trap: In Python/Java, string concatenation in a loop is O(n^2). Use lists/StringBuilder.
Palindrome thinking: Always consider expanding from center outward. Cheaper than checking all substrings.

Common Mistakes

Forgetting that Two Pointers requires sorted input (or you sort first)
Off-by-one errors in prefix sum: sum(i..j) = prefix[j+1] - prefix[i]
Not handling empty arrays / single-element arrays

Problems

#	Problem	Difficulty	Pattern	Status
1	Two Sum	Easy	HashMap	[ ]
2	Best Time to Buy and Sell Stock	Easy	Kadane's	[ ]
3	Contains Duplicate	Easy	HashSet	[ ]
4	Product of Array Except Self	Medium	Prefix/Suffix	[ ]
5	Maximum Subarray	Medium	DP / Greedy	[ ]
6	Maximum Product Subarray	Medium	Track min & max	[ ]
7	3Sum	Medium	Two Pointers	[ ]
8	Container With Most Water	Medium	Two Pointers	[ ]
9	Trapping Rain Water	Hard	Stack / Two Ptrs	[ ]
10	First Missing Positive	Hard	Index as hash	[ ]
11	Longest Palindromic Substring	Medium	Expand center	[ ]
12	Palindromic Substrings	Medium	Expand center	[ ]