// Problem: "Given an array of integers, return the two numbers
// that add up to a target sum."

// Before coding, clarify:
// - Can there be duplicates? (e.g., [3, 3] with target 6)
// - Will there always be exactly one solution?
// - Can I use the same element twice?
// - What range of values? (affects whether negative numbers matter)
// - Return indices or values?

// Problem: Two Sum — find indices of two numbers that add to target
// Input: nums = [2, 7, 11, 15], target = 9
// Expected: [0, 1]  (nums[0] + nums[1] = 2 + 7 = 9)

// Work through it by hand:
// i=0: nums[0]=2. Need 9-2=7. Have we seen 7? No. Record {2: 0}
// i=1: nums[1]=7. Need 9-7=2. Have we seen 2? YES at index 0. Return [0, 1]

// Edge cases to consider:
// nums = [],        target = 0    -> return [] or throw?
// nums = [3],       target = 6    -> no solution possible
// nums = [3, 3],    target = 6    -> [0, 1] — same value, different indices
// nums = [-1, 10],  target = 9    -> [0, 1] — negative numbers work fine
// nums = [0, 0],    target = 0    -> [0, 1]

// Two Sum — Step 1: Brute Force
// Check every pair of elements
function twoSum_brute(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
  return []
}
// Time: O(n^2) — two nested loops
// Space: O(1)

// Two Sum — Step 2: Identify the bottleneck
// The inner loop is asking: "have I seen (target - nums[i]) before?"
// That question can be answered in O(1) with a hash map!

// Two Sum — Step 3: Optimized
function twoSum_optimized(nums, target) {
  const seen = new Map()  // value -> index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]
    if (seen.has(complement)) {
      return [seen.get(complement), i]
    }
    seen.set(nums[i], i)
  }
  return []
}
// Time: O(n) — single pass
// Space: O(n) — hash map stores up to n entries

// Problem: Find the longest consecutive sequence in an array
// Input: [100, 4, 200, 1, 3, 2] -> Output: 4 (sequence 1,2,3,4)

// PSEUDOCODE:
// 1. Put all numbers in a hash set for O(1) lookup
// 2. For each number in the set:
//    a. Only start counting if it's the beginning of a sequence
//       (i.e., num-1 is NOT in the set)
//    b. From this starting number, count how far the sequence extends
//       by checking num+1, num+2, etc.
//    c. Update the global maximum length
// 3. Return the maximum length found

// Now translate to code:
function longestConsecutive(nums) {
  const numSet = new Set(nums)
  let maxLength = 0

  for (const num of numSet) {
    // Only start counting at sequence beginnings
    if (!numSet.has(num - 1)) {
      let current = num
      let length = 1

      while (numSet.has(current + 1)) {
        current++
        length++
      }

      maxLength = Math.max(maxLength, length)
    }
  }

  return maxLength
}
// Time: O(n) — each number is visited at most twice
// Space: O(n) — the hash set

// Function to dry-run:
function longestConsecutive([100, 4, 200, 1, 3, 2]) { ... }

// Dry-run trace:
// numSet = {100, 4, 200, 1, 3, 2}
// maxLength = 0

// Iteration 1: num = 100
//   numSet.has(99)? No -> start counting
//   current=100, length=1
//   numSet.has(101)? No -> stop
//   maxLength = max(0, 1) = 1

// Iteration 2: num = 4
//   numSet.has(3)? Yes -> skip (not a start)

// Iteration 3: num = 200
//   numSet.has(199)? No -> start counting
//   current=200, length=1
//   numSet.has(201)? No -> stop
//   maxLength = max(1, 1) = 1

// Iteration 4: num = 1
//   numSet.has(0)? No -> start counting
//   current=1, length=1
//   numSet.has(2)? Yes -> current=2, length=2
//   numSet.has(3)? Yes -> current=3, length=3
//   numSet.has(4)? Yes -> current=4, length=4
//   numSet.has(5)? No -> stop
//   maxLength = max(1, 4) = 4

// Iterations 5-6: num=3 and num=2
//   Both have predecessors in set -> skip

// Final: return maxLength = 4  ✓

// Testing longestConsecutive with edge cases:

console.log(longestConsecutive([]))           // Expected: 0
console.log(longestConsecutive([1]))          // Expected: 1
console.log(longestConsecutive([1, 1, 1]))    // Expected: 1 (duplicates)
console.log(longestConsecutive([1, 2, 3, 4])) // Expected: 4 (all consecutive)
console.log(longestConsecutive([4, 3, 2, 1])) // Expected: 4 (reverse order)
console.log(longestConsecutive([-3, -2, -1])) // Expected: 3 (negatives)
console.log(longestConsecutive([100, 4, 200, 1, 3, 2])) // Expected: 4

// Problem: "Given a string s, find the length of the longest
// substring without repeating characters."
// Input: "abcabcbb" -> Output: 3 (substring "abc")
// Input: "bbbbb"   -> Output: 1 (substring "b")
// Input: "pwwkew"  -> Output: 3 (substring "wke")

// R — Restate:
// Find the maximum window size in which all characters are unique.

// E — Examples:
// "abcabcbb": a,b,c then a repeats -> window [1..3] = "abc" length 3
// "":         empty -> 0
// "au":       both unique -> 2

// A — Approach (brute force first):
// Check every possible substring -> O(n^3) — too slow
// Better: sliding window — maintain a window [left, right] where all chars unique
//   - Expand right one char at a time
//   - When a duplicate is found, shrink left until the duplicate is removed
//   - Track maximum window size seen

// C — Code:
function lengthOfLongestSubstring(s) {
  const seen = new Map()  // char -> last index seen
  let left = 0
  let maxLen = 0

  for (let right = 0; right < s.length; right++) {
    const char = s[right]
    // If we've seen this char in our current window, move left past it
    if (seen.has(char) && seen.get(char) >= left) {
      left = seen.get(char) + 1
    }
    seen.set(char, right)
    maxLen = Math.max(maxLen, right - left + 1)
  }

  return maxLen
}

// T — Test:
// "abcabcbb":
//   right=0,a: seen={a:0}, left=0, len=1
//   right=1,b: seen={a:0,b:1}, left=0, len=2
//   right=2,c: seen={a:0,b:1,c:2}, left=0, len=3
//   right=3,a: a seen at 0 >= left(0), left=1, seen={a:3,b:1,c:2}, len=3
//   right=4,b: b seen at 1 >= left(1), left=2, seen={a:3,b:4,c:2}, len=3
//   right=5,c: c seen at 2 >= left(2), left=3, seen={a:3,b:4,c:5}, len=3
//   right=6,b: b seen at 4 >= left(3), left=5, seen={a:3,b:6,c:5}, len=2
//   right=7,b: b seen at 6 >= left(5), left=7, seen={a:3,b:7,c:5}, len=1
//   Result: 3  ✓

// O — Optimize: Already O(n) time, O(min(n, charset)) space — optimal!