Practice: Classic Array & String Problems

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 6 Time to complete: ~30 minutes

Table of Contents

1. Worked Example: Best Time to Buy and Sell Stock
2. Worked Example: Maximum Subarray (Kadane's Algorithm)
3. Worked Example: Valid Anagram, Revisited
4. Pattern Recap for This Module
5. Try It Yourself
6. Summary & Next Steps

1. Worked Example: Best Time to Buy and Sell Stock

Problem: Given daily prices, find the maximum profit from buying on one day and selling on a later day.

def max_profit(prices):
    if not prices:
        return 0
 
    min_price_so_far = prices[0]
    best_profit = 0
 
    for price in prices[1:]:
        best_profit = max(best_profit, price - min_price_so_far)
        min_price_so_far = min(min_price_so_far, price)
 
    return best_profit
    # O(n) time, O(1) space — a single pass, tracking the best "buy low" seen so far
 
print(max_profit([7, 1, 5, 3, 6, 4]))    # 5  (buy at 1, sell at 6)

Why this beats brute force: checking every buy/sell pair is O(n²). This solution recognizes that for any selling day, the best possible profit only depends on the lowest price seen before it — a single running variable, updated in one pass. This "track the best-so-far value while scanning" shape reappears throughout DSA.

2. Worked Example: Maximum Subarray (Kadane's Algorithm)

Problem: Find the contiguous subarray with the largest sum.

def max_subarray_sum(items):
    best_sum = items[0]
    current_sum = items[0]
 
    for item in items[1:]:
        current_sum = max(item, current_sum + item)   # extend, or start fresh here
        best_sum = max(best_sum, current_sum)
 
    return best_sum
    # O(n) time, O(1) space
 
print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))    # 6  ([4, -1, 2, 1])

The key decision at each step: should the current element extend the running subarray, or is the running sum so negative that it's better to start a brand-new subarray at the current element? That one comparison, applied once per element, is Kadane's algorithm in full — a strong example of how a seemingly "clever" algorithm often reduces to one well-chosen comparison per iteration.

3. Worked Example: Valid Anagram, Revisited

Using collections.Counter — the standard-library shortcut for the counting approach from Chapter 6:

from collections import Counter
 
def is_anagram(a, b):
    return Counter(a) == Counter(b)
    # O(n) time, O(1) space if the character set is bounded

Worth knowing both the manual dictionary version (Chapter 6) — which is what you'd write under interview pressure to demonstrate you understand the mechanism — and this Counter shortcut, which is what you'd actually reach for in production code.

4. Pattern Recap for This Module

5. Try It Yourself

# (a) Given an array, return True if any value appears at least twice.
def contains_duplicate(items):
    pass
 
# (b) Given a sorted array, move all zeros to the end while keeping the
#     relative order of non-zero elements, in place.
def move_zeros(items):
    pass
 
# (c) Given a string, find the length of the longest substring with at
#     most 2 distinct characters.
def longest_substring_two_distinct(s):
    pass

# (a) — hash set membership check, O(n) time, O(n) space
def contains_duplicate(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False
 
# (b) — same-direction two-pointer, O(n) time, O(1) space
def move_zeros(items):
    slow = 0
    for fast in range(len(items)):
        if items[fast] != 0:
            items[slow], items[fast] = items[fast], items[slow]
            slow += 1
    return items
 
# (c) — variable-size sliding window with a frequency dict, O(n) time, O(1) space
def longest_substring_two_distinct(s):
    counts = {}
    left = 0
    longest = 0
    for right in range(len(s)):
        counts[s[right]] = counts.get(s[right], 0) + 1
        while len(counts) > 2:
            counts[s[left]] -= 1
            if counts[s[left]] == 0:
                del counts[s[left]]
            left += 1
        longest = max(longest, right - left + 1)
    return longest

6. Summary & Next Steps

Key Takeaways

• "Track the best-so-far value in a single pass" (max profit, Kadane's) is as important a pattern as two-pointer and sliding window.
• Kadane's algorithm reduces to one comparison per element: extend the current subarray, or restart at the current element.
• collections.Counter is the idiomatic shortcut for frequency-counting problems once you understand the manual dictionary version.
• This module's patterns — two-pointer, sliding window, single-pass tracking, frequency counting — cover the large majority of array/string interview questions.

Concept Check

1. Why is tracking min_price_so_far while scanning once sufficient to solve the buy/sell stock problem, without checking every pair?
2. What's the one decision Kadane's algorithm makes at each element, and why does that decision alone produce the correct answer?
3. In the "Try It Yourself" answer for longest substring with at most 2 distinct characters, why does the while loop not make the algorithm O(n²)?

Next Module

→ Module 3: Searching & Sorting

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index