Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Crash Course: Introduction to Week 1, Part 1

General • Asked over 4 years ago by Team AlgoDaily

Team AlgoDaily Commented on Jan 02, 2021:

General discussion thread for the week 1, part 1 of the crash course.

Jun Commented on Jun 17, 2025:

If Week 1 / Part 1 is Big-O + arrays/strings, here’s a simple plan to get the most out of it:

  • Always write a brute-force first, then annotate time/space. Then optimize.
  • Know your language’s common op costs: dict/set avg O(1); list insert/delete middle O(n); slicing often O(k).
  • Pattern focus: two pointers, sliding window, and hash maps (frequency, index lookup).
  • Derive target complexity from constraints before coding (n up to 1e5 → avoid O(n2)).
  • Test edges: empty, single item, duplicates, negatives, unicode/whitespace, very large inputs.
  • Daily reps: 30–45 min. Suggested set: Two Sum, Valid Anagram, Move Zeroes, Max Subarray (Kadane), Longest Substring Without Repeating Characters.
  • Mini-challenge: implement Two Sum 1) brute-force, 2) sort + two pointers, 3) hash map; write Big-O for each.

If anything in the intro (esp. asymptotic analysis or sliding window) is fuzzy, drop your code or reasoning and I’ll point out where the complexity or logic goes off.

Pat Kumar Commented on Jun 21, 2025:

Jun’s plan is spot on. A few practical notes that help in interviews and on real projects:

  • Derive target complexity upfront: if n ≈ 1e5, aim O(n) or O(n log n). If you can’t hit it, explain tradeoffs.
  • Two Sum:
    • Brute: O(n2), no extra space.
    • Sort + two pointers: O(n log n). Remember sorting loses original indices—sort (value, index) pairs.
    • Hash map: O(n) time, O(n) space. Easiest to pass.
  • Sliding window (Longest Substring…): keep lastseen[char] = index, and move left = max(left, lastseen[c]+1). Each pointer moves ≤ n times → O(n).
  • Arrays/strings pitfalls:
    • Don’t slice in inner loops; s[i:j] copies → hidden O(k).
    • String concat in loops is O(n2); use list join or StringBuilder.
    • Unicode: length is code points, not bytes. Test with emojis/accents if relevant.
  • Move Zeroes: write pointer swaps nonzeros forward → O(n), in-place, stable.
  • Kadane: running best = max(num, best+num); track global max.

Great string drill: Valid Numeric String.
- Handle trims, optional sign, digits, optional decimal, optional exponent (e/E with signed integer).
- Edge tests: "0", " -3.5e+8 ", ".", ".1", "1.", "1e", "e9", "+.8", " ", "1e-2", "1e+02".
- Linear scan with a small state machine → O(n), O(1) space.

If anyone’s sliding window feels “O(n2)”, you’re likely shrinking the window one-by-one too often or rebuilding substrings—share the snippet and we can pinpoint it.

Ben Commented on Jun 30, 2025:

Jun/Pat’s notes are super helpful. Trying to internalize the sliding window rule. This is my Python for Longest Substring Without Repeating Characters:

python
def lengthOfLongestSubstring(s: str) -> int:
    last = {}
    left = 0
    best = 0
    for right, c in enumerate(s):
        if c in last and last[c] >= left:
            left = last[c] + 1
        last[c] = right
        best = max(best, right - left + 1)
    return best
  • Is this truly O(n) in Python? I’m avoiding slicing and concat, but does iterating Unicode (emojis) change anything complexity-wise?
  • Pat mentioned using max(left, last[c]+1). My conditional seems equivalent—are there edge cases where the max form is safer? I tested "abba" and it works, but curious if I’m missing something.

Also on Two Sum (sort + two pointers): if I sort (value, index) pairs to recover indices, does that count as O(n) extra space in interviews? Is there any way to do sort+two pointers and still claim O(1) extra without losing original indices?