"""
# LC 122: Best Time to Buy and Sell Stock II

You are given an integer array `prices` where `prices[i]` is the price of a
given stock on the i-th day. On each day, you may decide to buy and/or sell the
stock. You can only hold at most one share of the stock at any time. However,
you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

## Examples

```text
Input:  prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price=1), sell on day 3 (price=5), profit=4.
             Buy on day 4 (price=3), sell on day 5 (price=6), profit=3.
             Total profit = 7.

Input:  prices = [1,2,3,4,5]
Output: 4

Input:  prices = [7,6,4,3,1]
Output: 0
```

## Constraints
- 1 <= prices.length <= 3 * 10^4
- 0 <= prices[i] <= 10^4
"""
from typing import List


class Solution:
    def maxProfit_brute(self, prices: List[int]) -> int:
        """Recursion — O(2^n) time, O(n) stack space."""
        # Recursive DFS: at each day decide to buy, sell, or skip
        # Exponential without memoization — illustrates the decision tree
        def dfs(i: int, holding: bool) -> int:
            if i == len(prices):
                return 0
            # skip
            best = dfs(i + 1, holding)
            if holding:
                best = max(best, prices[i] + dfs(i + 1, False))
            else:
                best = max(best, -prices[i] + dfs(i + 1, True))
            return best
        return dfs(0, False)

    def maxProfit(self, prices: List[int]) -> int:
        """Greedy — O(n) time, O(1) space."""
        # Greedy: capture every upward price movement as profit
        # Equivalent to buying and selling on every consecutive rising day
        return sum(max(prices[i] - prices[i - 1], 0) for i in range(1, len(prices)))


if __name__ == "__main__":
    s = Solution()

    assert s.maxProfit([7, 1, 5, 3, 6, 4]) == 7
    assert s.maxProfit([1, 2, 3, 4, 5]) == 4
    assert s.maxProfit([7, 6, 4, 3, 1]) == 0
    assert s.maxProfit([1]) == 0

    print("All tests passed.")

"""
# LC 1929: Concatenation of Array

Given an integer array `nums` of length `n`, return an array `ans` of length `2n`
where `ans[i] == nums[i]` and `ans[i + n] == nums[i]` for all `0 <= i < n`.

## Examples

```text
Input:  nums = [1,2,1]
Output: [1,2,1,1,2,1]

Input:  nums = [1,3,2,1]
Output: [1,3,2,1,1,3,2,1]
```

## Constraints
- n == nums.length
- 1 <= n <= 1000
- 1 <= nums[i] <= 1000
"""
from typing import List


class Solution:
    def getConcatenation_brute(self, nums: List[int]) -> List[int]:
        # Append all elements twice using a loop
        # O(n) time | O(n) space
        ans = []
        for _ in range(2):
            for n in nums:
                ans.append(n)
        return ans

    def getConcatenation(self, nums: List[int]) -> List[int]:
        # Python list concatenation creates a new list with both copies
        # O(n) time | O(n) space
        return nums + nums


if __name__ == "__main__":
    s = Solution()
    assert s.getConcatenation([1, 2, 1]) == [1, 2, 1, 1, 2, 1]
    assert s.getConcatenation([1, 3, 2, 1]) == [1, 3, 2, 1, 1, 3, 2, 1]
    print("All tests passed.")

"""
# LC 217: Contains Duplicate

Given an integer array `nums`, return `true` if any value appears **at least twice**,
and return `false` if every element is distinct.

## Examples

```text
Input:  nums = [1,2,3,1]
Output: true

Input:  nums = [1,2,3,4]
Output: false

Input:  nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
```

## Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
"""
from typing import List


class Solution:
    def containsDuplicate_brute(self, nums: List[int]) -> bool:
        # Compare every pair — O(n^2); fine for small inputs
        # O(n^2) time | O(1) space
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] == nums[j]:
                    return True
        return False

    def containsDuplicate_sort(self, nums: List[int]) -> bool:
        # After sorting, duplicates are adjacent — one linear scan suffices
        # O(n log n) time | O(1) space
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                return True
        return False

    def containsDuplicate(self, nums: List[int]) -> bool:
        # A set collapses duplicates; if lengths differ, a duplicate existed
        # O(n) time | O(n) space
        return len(nums) != len(set(nums))


if __name__ == "__main__":
    s = Solution()
    assert s.containsDuplicate([1, 2, 3, 1]) == True
    assert s.containsDuplicate([1, 2, 3, 4]) == False
    assert s.containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]) == True
    print("All tests passed.")

"""
# LC 706: Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement `MyHashMap`:
- `put(key, value)` — Inserts a `(key, value)` pair. Updates value if key exists.
- `get(key)` — Returns the value mapped to `key`, or `-1` if not present.
- `remove(key)` — Removes the `key` and its value if present.

## Examples

```text
Input:
  ["MyHashMap","put","put","get","get","put","get","remove","get"]
  [[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]
Output:
  [null,null,null,1,-1,null,1,null,-1]
```

## Constraints
- 0 <= key, value <= 10^6
- At most 10^4 calls will be made to put, get, and remove.
"""


# Approach 1: Array-based — O(1) time | O(10^6) space
class MyHashMap:
    def __init__(self):
        self.data = [-1] * (10**6 + 1)

    def put(self, key: int, value: int) -> None:
        self.data[key] = value

    def get(self, key: int) -> int:
        return self.data[key]

    def remove(self, key: int) -> None:
        self.data[key] = -1


# Approach 2: Chaining with lists of (key, value) pairs — O(1) avg time | O(n) space
class MyHashMapChaining:
    def __init__(self):
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]

    def _hash(self, key: int) -> int:
        return key % self.size

    def put(self, key: int, value: int) -> None:
        h = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[h]):
            if k == key:
                self.buckets[h][i] = (key, value)
                return
        self.buckets[h].append((key, value))

    def get(self, key: int) -> int:
        for k, v in self.buckets[self._hash(key)]:
            if k == key:
                return v
        return -1

    def remove(self, key: int) -> None:
        h = self._hash(key)
        self.buckets[h] = [(k, v) for k, v in self.buckets[h] if k != key]


if __name__ == "__main__":
    hm = MyHashMap()
    hm.put(1, 1)
    hm.put(2, 2)
    assert hm.get(1) == 1
    assert hm.get(3) == -1
    hm.put(2, 1)
    assert hm.get(2) == 1
    hm.remove(2)
    assert hm.get(2) == -1
    print("All tests passed.")

"""
# LC 705: Design HashSet

Design a HashSet without using any built-in hash table libraries.

Implement `MyHashSet`:
- `add(key)` — Inserts the value `key` into the HashSet.
- `remove(key)` — Removes the value `key` in the HashSet. If `key` does not exist, do nothing.
- `contains(key)` — Returns whether the value `key` exists in the HashSet or not.

## Examples

```text
Input:
  ["MyHashSet","add","add","contains","contains","add","contains","remove","contains"]
  [[],[1],[2],[1],[3],[2],[2],[2],[2]]
Output:
  [null,null,null,true,false,null,true,null,false]
```

## Constraints
- 0 <= key <= 10^6
- At most 10^4 calls will be made to add, remove, and contains.
"""


# Approach 1: Boolean array — O(1) time | O(10^6) space
class MyHashSet:
    def __init__(self):
        self.data = [False] * (10**6 + 1)

    def add(self, key: int) -> None:
        self.data[key] = True

    def remove(self, key: int) -> None:
        self.data[key] = False

    def contains(self, key: int) -> bool:
        return self.data[key]


# Approach 2: Chaining with lists — O(1) avg time | O(n) space
class MyHashSetChaining:
    def __init__(self):
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]

    def _hash(self, key: int) -> int:
        return key % self.size

    def add(self, key: int) -> None:
        h = self._hash(key)
        if key not in self.buckets[h]:
            self.buckets[h].append(key)

    def remove(self, key: int) -> None:
        h = self._hash(key)
        if key in self.buckets[h]:
            self.buckets[h].remove(key)

    def contains(self, key: int) -> bool:
        return key in self.buckets[self._hash(key)]


if __name__ == "__main__":
    hs = MyHashSet()
    hs.add(1)
    hs.add(2)
    assert hs.contains(1) == True
    assert hs.contains(3) == False
    hs.add(2)
    assert hs.contains(2) == True
    hs.remove(2)
    assert hs.contains(2) == False
    print("All tests passed.")

"""
# LC 271: Encode and Decode Strings

Design an algorithm to encode a list of strings to a single string. The encoded
string is then sent over the network and is decoded back to the original list of
strings.

## Examples

```text
Input:  strs = ["Hello","World"]
Encoded: "5#Hello5#World"
Output: ["Hello","World"]

Input:  strs = [""]
Output: [""]
```

## Constraints
- 0 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] contains any possible characters out of 256 valid ASCII characters
"""
from typing import List


class Codec:
    def encode(self, strs: List[str]) -> str:
        """Delimiter with escaping — O(n) time."""
        # Prefix each string with its length and '#' as delimiter
        # This handles strings containing any character including '#'
        return "".join(f"{len(s)}#{s}" for s in strs)

    def decode(self, s: str) -> List[str]:
        """Length-prefix decoding — O(n) time."""
        # Read length prefix up to '#', then extract exactly that many chars
        # Advance i past the extracted string to process the next one
        result, i = [], 0
        while i < len(s):
            j = s.index("#", i)
            length = int(s[i:j])
            result.append(s[j + 1: j + 1 + length])
            i = j + 1 + length
        return result


if __name__ == "__main__":
    codec = Codec()

    for strs in [
        ["Hello", "World"],
        [""],
        [],
        ["a#b", "c#d"],
        ["with spaces", "and\nnewlines"],
    ]:
        assert codec.decode(codec.encode(strs)) == strs, strs

    print("All tests passed.")

"""
# LC 41: First Missing Positive

Given an unsorted integer array `nums`, return the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

## Examples

```text
Input:  nums = [1,2,0]
Output: 3

Input:  nums = [3,4,-1,1]
Output: 2

Input:  nums = [7,8,9,11,12]
Output: 1
```

## Constraints
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
"""
from typing import List


class Solution:
    def firstMissingPositive_hashset(self, nums: List[int]) -> int:
        """Hash set — O(n) time, O(n) space."""
        # Store all numbers in a set, then probe 1, 2, 3... for the first gap
        s = set(nums)
        i = 1
        while i in s:
            i += 1
        return i

    def firstMissingPositive(self, nums: List[int]) -> int:
        """Index marking (cyclic sort idea) — O(n) time, O(1) space."""
        # Cyclic sort: place each number at index nums[i]-1 if in range [1,n]
        # After rearranging, the first index where nums[i] != i+1 is the answer
        # If all positions are correct, the answer is n+1
        n = len(nums)
        # Place each number in its correct index position (nums[i] == i+1)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1


if __name__ == "__main__":
    s = Solution()

    assert s.firstMissingPositive([1, 2, 0]) == 3
    assert s.firstMissingPositive([3, 4, -1, 1]) == 2
    assert s.firstMissingPositive([7, 8, 9, 11, 12]) == 1
    assert s.firstMissingPositive([1]) == 2
    assert s.firstMissingPositive([1, 2, 3]) == 4

    print("All tests passed.")

"""
# LC 49: Group Anagrams

Given an array of strings `strs`, group the anagrams together. You can return
the answer in any order.

## Examples

```text
Input:  strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Input:  strs = [""]
Output: [[""]]

Input:  strs = ["a"]
Output: [["a"]]
```

## Constraints
- 1 <= strs.length <= 10^4
- 0 <= strs[i].length <= 100
- strs[i] consists of lowercase English letters.
"""
from typing import List
from collections import defaultdict


class Solution:
    def groupAnagrams_sort(self, strs: List[str]) -> List[List[str]]:
        # Sorted string is a canonical key — all anagrams share the same key
        # O(n * k log k) time | O(n * k) space
        groups = defaultdict(list)
        for s in strs:
            groups[tuple(sorted(s))].append(s)
        return list(groups.values())

    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # Character-frequency tuple is a canonical key without sorting cost
        # Build a 26-element count array per word, then use it as dict key
        # O(n * k) time | O(n * k) space
        groups = defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            groups[tuple(count)].append(s)
        return list(groups.values())


if __name__ == "__main__":
    s = Solution()
    result = s.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
    assert sorted(sorted(g) for g in result) == [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
    assert s.groupAnagrams([""]) == [[""]]
    assert s.groupAnagrams(["a"]) == [["a"]]
    print("All tests passed.")

"""
# LC 14: Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string `""`.

## Examples

```text
Input:  strs = ["flower","flow","flight"]
Output: "fl"

Input:  strs = ["dog","racecar","car"]
Output: ""
```

## Constraints
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] consists of only lowercase English letters.
"""
from typing import List


class Solution:
    def longestCommonPrefix_vertical(self, strs: List[str]) -> str:
        # Check each character position across all strings simultaneously
        # Stop as soon as any string diverges or runs out of characters
        # O(S) time where S = sum of all characters | O(1) space
        if not strs:
            return ""
        for i, ch in enumerate(strs[0]):
            for s in strs[1:]:
                if i >= len(s) or s[i] != ch:
                    return strs[0][:i]
        return strs[0]

    def longestCommonPrefix(self, strs: List[str]) -> str:
        # After sorting, only the first and last strings need to be compared
        # The common prefix of extremes is the common prefix of all strings
        # O(n log n * m) time | O(1) space
        strs.sort()
        first, last = strs[0], strs[-1]
        i = 0
        while i < len(first) and i < len(last) and first[i] == last[i]:
            i += 1
        return first[:i]


if __name__ == "__main__":
    s = Solution()
    assert s.longestCommonPrefix(["flower", "flow", "flight"]) == "fl"
    assert s.longestCommonPrefix(["dog", "racecar", "car"]) == ""
    assert s.longestCommonPrefix(["interview", "interact", "interface"]) == "inter"
    print("All tests passed.")

"""
# LC 128: Longest Consecutive Sequence

Given an unsorted array of integers `nums`, return the length of the longest
consecutive elements sequence. You must write an algorithm that runs in O(n) time.

## Examples

```text
Input:  nums = [100,4,200,1,3,2]
Output: 4
Explanation: [1,2,3,4]

Input:  nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
```

## Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
"""
from typing import List


class Solution:
    def longestConsecutive_sort(self, nums: List[int]) -> int:
        """Sorting — O(n log n) time, O(1) extra space."""
        # After deduplication and sorting, consecutive elements differ by 1
        if not nums:
            return 0
        nums = sorted(set(nums))
        best = cur = 1
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1] + 1:
                cur += 1
                best = max(best, cur)
            else:
                cur = 1
        return best

    def longestConsecutive(self, nums: List[int]) -> int:
        """Hash set — O(n) time, O(n) space."""
        # Only start counting from the beginning of a sequence (n-1 not in set)
        # This ensures each sequence is counted exactly once — O(n) total
        num_set = set(nums)
        best = 0
        for n in num_set:
            if n - 1 not in num_set:
                cur = 1
                while n + cur in num_set:
                    cur += 1
                best = max(best, cur)
        return best


if __name__ == "__main__":
    s = Solution()

    assert s.longestConsecutive([100, 4, 200, 1, 3, 2]) == 4
    assert s.longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) == 9
    assert s.longestConsecutive([]) == 0
    assert s.longestConsecutive([1]) == 1

    print("All tests passed.")

"""
# LC 169: Majority Element

Given an array `nums` of size `n`, return the majority element — the element that
appears more than `⌊n / 2⌋` times. The majority element always exists.

## Examples

```text
Input:  nums = [3,2,3]
Output: 3

Input:  nums = [2,2,1,1,1,2,2]
Output: 2
```

## Constraints
- n == nums.length
- 1 <= n <= 5 * 10^4
- -10^9 <= nums[i] <= 10^9
- The majority element always exists.
"""
from typing import List
from collections import Counter


class Solution:
    def majorityElement_map(self, nums: List[int]) -> int:
        # Count occurrences and return the element with the highest count
        # O(n) time | O(n) space
        count = Counter(nums)
        return max(count, key=count.get)

    def majorityElement_sort(self, nums: List[int]) -> int:
        # The majority element always occupies the middle index after sorting
        # O(n log n) time | O(1) space
        nums.sort()
        return nums[len(nums) // 2]

    def majorityElement(self, nums: List[int]) -> int:
        # Boyer-Moore: maintain a candidate and a net vote count
        # When count hits 0, the current element becomes the new candidate
        # Majority element's votes always outlast all opposition combined
        # O(n) time | O(1) space — Boyer-Moore Voting
        candidate, count = None, 0
        for n in nums:
            if count == 0:
                candidate = n
            count += 1 if n == candidate else -1
        return candidate


if __name__ == "__main__":
    s = Solution()
    assert s.majorityElement([3, 2, 3]) == 3
    assert s.majorityElement([2, 2, 1, 1, 1, 2, 2]) == 2
    assert s.majorityElement([1]) == 1
    print("All tests passed.")

"""
# LC 229: Majority Element II

Given an integer array of size `n`, find all elements that appear more than
⌊n/3⌋ times.

## Examples

```text
Input:  nums = [3,2,3]
Output: [3]

Input:  nums = [1]
Output: [1]

Input:  nums = [1,2]
Output: [1,2]
```

## Constraints
- 1 <= nums.length <= 5 * 10^4
- -10^9 <= nums[i] <= 10^9
"""
from typing import List
from collections import Counter


class Solution:
    def majorityElement_hashmap(self, nums: List[int]) -> List[int]:
        """Hash map counting — O(n) time, O(n) space."""
        # Count all elements; return those appearing more than n//3 times
        threshold = len(nums) // 3
        return [num for num, cnt in Counter(nums).items() if cnt > threshold]

    def majorityElement(self, nums: List[int]) -> List[int]:
        """Boyer-Moore extended (at most 2 candidates) — O(n) time, O(1) space."""
        # At most 2 elements can appear more than n/3 times
        # Maintain two candidates with vote counts; cancel out different pairs
        # Final verification pass confirms candidates actually exceed threshold
        cand1, cand2, cnt1, cnt2 = 0, 1, 0, 0
        for n in nums:
            if n == cand1:
                cnt1 += 1
            elif n == cand2:
                cnt2 += 1
            elif cnt1 == 0:
                cand1, cnt1 = n, 1
            elif cnt2 == 0:
                cand2, cnt2 = n, 1
            else:
                cnt1 -= 1
                cnt2 -= 1
        threshold = len(nums) // 3
        return [c for c in (cand1, cand2) if nums.count(c) > threshold]


if __name__ == "__main__":
    s = Solution()

    assert sorted(s.majorityElement([3, 2, 3])) == [3]
    assert sorted(s.majorityElement([1])) == [1]
    assert sorted(s.majorityElement([1, 2])) == [1, 2]
    assert sorted(s.majorityElement([1, 1, 1, 3, 3, 2, 2, 2])) == [1, 2]

    print("All tests passed.")

"""
# LC 238: Product of Array Except Self

Given an integer array `nums`, return an array `answer` such that `answer[i]`
is equal to the product of all the elements of `nums` except `nums[i]`.

The product of any prefix or suffix of `nums` is guaranteed to fit in a 32-bit
integer. You must write an algorithm that runs in O(n) time and without using
the division operation.

## Examples

```text
Input:  nums = [1,2,3,4]
Output: [24,12,8,6]

Input:  nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
```

## Constraints
- 2 <= nums.length <= 10^5
- -30 <= nums[i] <= 30
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer
"""
from typing import List


class Solution:
    def productExceptSelf_brute(self, nums: List[int]) -> List[int]:
        """Brute force — O(n^2) time, O(1) extra space."""
        # For each position, multiply all other elements — O(n^2)
        n = len(nums)
        answer = []
        for i in range(n):
            p = 1
            for j in range(n):
                if j != i:
                    p *= nums[j]
            answer.append(p)
        return answer

    def productExceptSelf_prefix_suffix(self, nums: List[int]) -> List[int]:
        """Prefix and suffix arrays — O(n) time, O(n) space."""
        # prefix[i] = product of all elements to the LEFT of i
        # suffix[i] = product of all elements to the RIGHT of i
        # answer[i] = prefix[i] * suffix[i] — no division needed
        n = len(nums)
        prefix = [1] * n
        suffix = [1] * n
        for i in range(1, n):
            prefix[i] = prefix[i - 1] * nums[i - 1]
        for i in range(n - 2, -1, -1):
            suffix[i] = suffix[i + 1] * nums[i + 1]
        return [prefix[i] * suffix[i] for i in range(n)]

    def productExceptSelf(self, nums: List[int]) -> List[int]:
        """Single output array — O(n) time, O(1) extra space."""
        # First pass: fill answer[i] with running left-product up to i-1
        # Second pass: multiply in running right-product from i+1 onward
        # This avoids the O(n) extra arrays by reusing the output array
        n = len(nums)
        answer = [1] * n
        prefix = 1
        for i in range(n):
            answer[i] = prefix
            prefix *= nums[i]
        suffix = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]
        return answer


if __name__ == "__main__":
    s = Solution()

    assert s.productExceptSelf([1, 2, 3, 4]) == [24, 12, 8, 6]
    assert s.productExceptSelf([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]
    assert s.productExceptSelf([1, 1]) == [1, 1]

    print("All tests passed.")

"""
# LC 304: Range Sum Query 2D - Immutable

Given a 2D matrix `matrix`, handle multiple queries of the following type:
Calculate the sum of the elements of `matrix` inside the rectangle defined by
its upper left corner `(row1, col1)` and lower right corner `(row2, col2)`.

Implement the `NumMatrix` class with efficient repeated queries.

## Examples

```text
matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
```

## Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- -10^4 <= matrix[i][j] <= 10^4
- 0 <= row1 <= row2 < m
- 0 <= col1 <= col2 < n
- At most 10^4 calls will be made to sumRegion
"""
from typing import List


class NumMatrixBrute:
    """Brute force — O(m*n) per query, O(1) extra space."""

    def __init__(self, matrix: List[List[int]]) -> None:
        self.matrix = matrix

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return sum(
            self.matrix[r][c]
            for r in range(row1, row2 + 1)
            for c in range(col1, col2 + 1)
        )


class NumMatrix:
    """2D prefix sum — O(m*n) build, O(1) per query."""

    def __init__(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
        for r in range(1, m + 1):
            for c in range(1, n + 1):
                self.prefix[r][c] = (
                    matrix[r - 1][c - 1]
                    + self.prefix[r - 1][c]
                    + self.prefix[r][c - 1]
                    - self.prefix[r - 1][c - 1]
                )

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        p = self.prefix
        return (
            p[row2 + 1][col2 + 1]
            - p[row1][col2 + 1]
            - p[row2 + 1][col1]
            + p[row1][col1]
        )


if __name__ == "__main__":
    matrix = [
        [3, 0, 1, 4, 2],
        [5, 6, 3, 2, 1],
        [1, 2, 0, 1, 5],
        [4, 1, 0, 1, 7],
        [1, 0, 3, 0, 5],
    ]
    nm = NumMatrix(matrix)
    assert nm.sumRegion(2, 1, 4, 3) == 8
    assert nm.sumRegion(1, 1, 2, 2) == 11
    assert nm.sumRegion(1, 2, 2, 4) == 12

    print("All tests passed.")

"""
# LC 27: Remove Element

Given an integer array `nums` and an integer `val`, remove all occurrences of `val`
in `nums` **in-place**. The order of the elements may be changed. Return the number
of elements in `nums` which are not equal to `val`.

## Examples

```text
Input:  nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]

Input:  nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
```

## Constraints
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 50
- 0 <= val <= 100
"""
from typing import List


class Solution:
    def removeElement_brute(self, nums: List[int], val: int) -> int:
        # Shift all elements left when val found — O(n^2) due to shifting
        # O(n^2) time | O(1) space
        i = 0
        while i < len(nums):
            if nums[i] == val:
                for j in range(i, len(nums) - 1):
                    nums[j] = nums[j + 1]
                nums.pop()
            else:
                i += 1
        return len(nums)

    def removeElement(self, nums: List[int], val: int) -> int:
        # k tracks the write position for non-val elements
        # Only advance k when we copy a valid element — O(n) single pass
        # O(n) time | O(1) space
        k = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[k] = nums[i]
                k += 1
        return k


if __name__ == "__main__":
    s = Solution()
    nums = [3, 2, 2, 3]
    assert s.removeElement(nums, 3) == 2 and nums[:2] == [2, 2]

    nums = [0, 1, 2, 2, 3, 0, 4, 2]
    assert s.removeElement(nums, 2) == 5 and sorted(nums[:5]) == [0, 0, 1, 3, 4]
    print("All tests passed.")

"""
# LC 912: Sort an Array

Given an array of integers `nums`, sort the array in ascending order and return it.
You must solve the problem **without using any built-in functions** in O(n log n)
time complexity and with the smallest space complexity possible.

## Examples

```text
Input:  nums = [5,2,3,1]
Output: [1,2,3,5]

Input:  nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
```

## Constraints
- 1 <= nums.length <= 5 * 10^4
- -5 * 10^4 <= nums[i] <= 5 * 10^4
"""
from typing import List
import random


class Solution:
    # Approach 1: Merge Sort — O(n log n) time | O(n) space
    def sortArray_merge(self, nums: List[int]) -> List[int]:
        # Divide array in half recursively until single elements, then merge
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2
        left = self.sortArray_merge(nums[:mid])
        right = self.sortArray_merge(nums[mid:])
        return self._merge(left, right)

    def _merge(self, left, right):
        # Merge two sorted halves by comparing front elements one at a time
        result, i, j = [], 0, 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i]); i += 1
            else:
                result.append(right[j]); j += 1
        return result + left[i:] + right[j:]

    # Approach 2: Quick Sort — O(n log n) avg | O(log n) space
    def sortArray_quick(self, nums: List[int]) -> List[int]:
        # Randomized pivot avoids worst-case O(n^2) on sorted input
        self._quick(nums, 0, len(nums) - 1)
        return nums

    def _quick(self, nums, lo, hi):
        # Partition around pivot, then recursively sort both halves
        if lo >= hi:
            return
        pivot_idx = self._partition(nums, lo, hi)
        self._quick(nums, lo, pivot_idx - 1)
        self._quick(nums, pivot_idx + 1, hi)

    def _partition(self, nums, lo, hi):
        # Randomly swap pivot to end, then move all <= pivot to the left
        rand = random.randint(lo, hi)
        nums[rand], nums[hi] = nums[hi], nums[rand]
        pivot, i = nums[hi], lo - 1
        for j in range(lo, hi):
            if nums[j] <= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1], nums[hi] = nums[hi], nums[i + 1]
        return i + 1

    # Approach 3: Heap Sort — O(n log n) time | O(1) space
    def sortArray(self, nums: List[int]) -> List[int]:
        # Heap sort: build max-heap, then repeatedly extract max to end
        n = len(nums)
        for i in range(n // 2 - 1, -1, -1):
            self._heapify(nums, n, i)
        for i in range(n - 1, 0, -1):
            nums[0], nums[i] = nums[i], nums[0]
            self._heapify(nums, i, 0)
        return nums

    def _heapify(self, nums, n, i):
        # Sift down: swap with largest child to maintain heap property
        largest, l, r = i, 2 * i + 1, 2 * i + 2
        if l < n and nums[l] > nums[largest]:
            largest = l
        if r < n and nums[r] > nums[largest]:
            largest = r
        if largest != i:
            nums[i], nums[largest] = nums[largest], nums[i]
            self._heapify(nums, n, largest)


if __name__ == "__main__":
    s = Solution()
    assert s.sortArray([5, 2, 3, 1]) == [1, 2, 3, 5]
    assert s.sortArray([5, 1, 1, 2, 0, 0]) == [0, 0, 1, 1, 2, 5]
    assert s.sortArray([-4, 0, 7, 4, 9, -5, -1, 0, -7, -1]) == sorted([-4, 0, 7, 4, 9, -5, -1, 0, -7, -1])
    print("All tests passed.")

"""
# LC 75: Sort Colors

Given an array `nums` with `n` objects colored red, white, or blue, sort them
in-place so that objects of the same color are adjacent, with the colors in the
order red, white, and blue. Use integers 0, 1, and 2 to represent red, white,
and blue respectively.

You must solve this without using the library's sort function.

## Examples

```text
Input:  nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Input:  nums = [2,0,1]
Output: [0,1,2]
```

## Constraints
- n == nums.length
- 1 <= n <= 300
- nums[i] is either 0, 1, or 2
"""
from typing import List


class Solution:
    def sortColors_counting(self, nums: List[int]) -> None:
        """Counting sort — O(n) time, O(1) space, two-pass."""
        # Count 0s, 1s, 2s then overwrite array in order — two passes
        count = [0, 0, 0]
        for n in nums:
            count[n] += 1
        i = 0
        for val, cnt in enumerate(count):
            for _ in range(cnt):
                nums[i] = val
                i += 1

    def sortColors(self, nums: List[int]) -> None:
        """Dutch National Flag — O(n) time, O(1) space, one-pass."""
        # Dutch National Flag: three regions — [0..lo-1]=0, [lo..mid-1]=1, [hi+1..n-1]=2
        # If mid is 0: swap with lo (both advance), if 1: advance mid, if 2: swap with hi
        # hi shrinks but mid doesn't advance after swap with hi (unknown value)
        lo, mid, hi = 0, 0, len(nums) - 1
        while mid <= hi:
            if nums[mid] == 0:
                nums[lo], nums[mid] = nums[mid], nums[lo]
                lo += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[hi] = nums[hi], nums[mid]
                hi -= 1


if __name__ == "__main__":
    s = Solution()

    nums = [2, 0, 2, 1, 1, 0]
    s.sortColors(nums)
    assert nums == [0, 0, 1, 1, 2, 2], nums

    nums = [2, 0, 1]
    s.sortColors(nums)
    assert nums == [0, 1, 2], nums

    nums = [0]
    s.sortColors(nums)
    assert nums == [0], nums

    print("All tests passed.")

"""
# LC 560: Subarray Sum Equals K

Given an array of integers `nums` and an integer `k`, return the total number
of subarrays whose sum equals to `k`.

A subarray is a contiguous non-empty sequence of elements within an array.

## Examples

```text
Input:  nums = [1,1,1], k = 2
Output: 2

Input:  nums = [1,2,3], k = 3
Output: 2
```

## Constraints
- 1 <= nums.length <= 2 * 10^4
- -1000 <= nums[i] <= 1000
- -10^7 <= k <= 10^7
"""
from typing import List
from collections import defaultdict


class Solution:
    def subarraySum_brute(self, nums: List[int], k: int) -> int:
        """Brute force — O(n^2) time, O(1) space."""
        # Try all subarrays starting at i — O(n^2)
        count = 0
        for i in range(len(nums)):
            total = 0
            for j in range(i, len(nums)):
                total += nums[j]
                if total == k:
                    count += 1
        return count

    def subarraySum(self, nums: List[int], k: int) -> int:
        """Prefix sum with hash map — O(n) time, O(n) space."""
        # prefix[j] - prefix[i] == k  =>  prefix[i] == prefix[j] - k
        # Store how many times each prefix sum has occurred
        # freq[0]=1 handles subarrays starting from index 0
        count = 0
        prefix = 0
        freq: dict = defaultdict(int)
        freq[0] = 1
        for n in nums:
            prefix += n
            count += freq[prefix - k]
            freq[prefix] += 1
        return count


if __name__ == "__main__":
    s = Solution()

    assert s.subarraySum([1, 1, 1], 2) == 2
    assert s.subarraySum([1, 2, 3], 3) == 2
    assert s.subarraySum([1], 0) == 0
    assert s.subarraySum([-1, -1, 1], 0) == 1

    print("All tests passed.")

"""
# LC 347: Top K Frequent Elements

Given an integer array `nums` and an integer `k`, return the `k` most frequent
elements. You may return the answer in any order.

## Examples

```text
Input:  nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Input:  nums = [1], k = 1
Output: [1]
```

## Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- k is in the range [1, the number of unique elements in the array]
- The answer is guaranteed to be unique
"""
from typing import List
from collections import Counter
import heapq


class Solution:
    def topKFrequent_sort(self, nums: List[int], k: int) -> List[int]:
        """Sort by frequency — O(n log n) time, O(n) space."""
        # Count frequencies, then sort by descending frequency and take top k
        count = Counter(nums)
        return sorted(count, key=lambda x: -count[x])[:k]

    def topKFrequent_heap(self, nums: List[int], k: int) -> List[int]:
        """Min-heap of size k — O(n log k) time, O(n) space."""
        # heapq.nlargest keeps a min-heap of size k — O(n log k)
        count = Counter(nums)
        return heapq.nlargest(k, count, key=count.get)

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        """Bucket sort — O(n) time, O(n) space."""
        # Bucket sort: index = frequency, so we can iterate buckets in reverse
        # Collect elements from highest-frequency bucket down until we have k
        count = Counter(nums)
        buckets: List[List[int]] = [[] for _ in range(len(nums) + 1)]
        for num, freq in count.items():
            buckets[freq].append(num)
        result: List[int] = []
        for freq in range(len(buckets) - 1, 0, -1):
            for num in buckets[freq]:
                result.append(num)
                if len(result) == k:
                    return result
        return result


if __name__ == "__main__":
    s = Solution()

    assert sorted(s.topKFrequent([1, 1, 1, 2, 2, 3], 2)) == [1, 2]
    assert s.topKFrequent([1], 1) == [1]
    assert sorted(s.topKFrequent([1, 2], 2)) == [1, 2]

    print("All tests passed.")

"""
# LC 1: Two Sum

Given an array of integers `nums` and an integer `target`, return *indices* of the
two numbers such that they add up to `target`. You may assume exactly one solution
exists, and you may not use the same element twice.

## Examples

```text
Input:  nums = [2,7,11,15], target = 9
Output: [0,1]

Input:  nums = [3,2,4], target = 6
Output: [1,2]

Input:  nums = [3,3], target = 6
Output: [0,1]
```

## Constraints
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Only one valid answer exists.
"""
from typing import List


class Solution:
    def twoSum_brute(self, nums: List[int], target: int) -> List[int]:
        # Try every pair (i, j) — O(n^2) because we check all combinations
        # O(n^2) time | O(1) space
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Use a hash map to remember each number's index as we scan
        # For each number, compute what complement is needed to reach target
        # If complement already seen, we found our pair in O(1) lookup
        # O(n) time | O(n) space
        seen = {}
        for i, n in enumerate(nums):
            diff = target - n
            if diff in seen:
                return [seen[diff], i]
            seen[n] = i
        return []


if __name__ == "__main__":
    s = Solution()
    assert s.twoSum([2, 7, 11, 15], 9) == [0, 1]
    assert s.twoSum([3, 2, 4], 6) == [1, 2]
    assert s.twoSum([3, 3], 6) == [0, 1]
    print("All tests passed.")

"""
# LC 242: Valid Anagram

Given two strings `s` and `t`, return `true` if `t` is an anagram of `s`,
and `false` otherwise.

## Examples

```text
Input:  s = "anagram", t = "nagaram"
Output: true

Input:  s = "rat", t = "car"
Output: false
```

## Constraints
- 1 <= s.length, t.length <= 5 * 10^4
- s and t consist of lowercase English letters
"""


class Solution:
    def isAnagram_sort(self, s: str, t: str) -> bool:
        # Sorting both strings makes them identical iff they're anagrams
        # O(n log n) time | O(1) space
        return sorted(s) == sorted(t)

    def isAnagram(self, s: str, t: str) -> bool:
        # Early exit if lengths differ — anagrams must have same length
        # Increment count for s's char, decrement for t's char simultaneously
        # All zeros at the end means every character balanced out
        # O(n) time | O(1) space — at most 26 keys
        if len(s) != len(t):
            return False
        count = [0] * 26
        for a, b in zip(s, t):
            count[ord(a) - ord('a')] += 1
            count[ord(b) - ord('a')] -= 1
        return all(c == 0 for c in count)


if __name__ == "__main__":
    s = Solution()
    assert s.isAnagram("anagram", "nagaram") == True
    assert s.isAnagram("rat", "car") == False
    assert s.isAnagram("a", "ab") == False
    print("All tests passed.")

"""
# LC 36: Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be
validated according to the following rules:
1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the nine 3 x 3 sub-boxes must contain the digits 1-9 without repetition.

Note: A Sudoku board (partially filled) could be valid but is not necessarily solvable.

## Examples

```text
Input: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Input: board with "8" appearing twice in the first row -> false
```

## Constraints
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit 1-9 or '.'
"""
from typing import List
from collections import defaultdict


class Solution:
    def isValidSudoku_brute(self, board: List[List[str]]) -> bool:
        """Check rows, cols, boxes separately — O(1) time/space."""
        # Check each row, column, and 3x3 box for duplicates separately
        for i in range(9):
            row = [x for x in board[i] if x != "."]
            col = [board[r][i] for r in range(9) if board[r][i] != "."]
            if len(row) != len(set(row)) or len(col) != len(set(col)):
                return False
        for br in range(3):
            for bc in range(3):
                box = [
                    board[br * 3 + r][bc * 3 + c]
                    for r in range(3)
                    for c in range(3)
                    if board[br * 3 + r][bc * 3 + c] != "."
                ]
                if len(box) != len(set(box)):
                    return False
        return True

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        """Single pass with hash sets — O(1) time/space."""
        # Single pass: track seen values per row, column, and box simultaneously
        # Box index is (r//3, c//3) — maps each cell to its 3x3 region
        # If a value already exists in any of the three sets, board is invalid
        rows = defaultdict(set)
        cols = defaultdict(set)
        boxes = defaultdict(set)
        for r in range(9):
            for c in range(9):
                val = board[r][c]
                if val == ".":
                    continue
                box = (r // 3, c // 3)
                if val in rows[r] or val in cols[c] or val in boxes[box]:
                    return False
                rows[r].add(val)
                cols[c].add(val)
                boxes[box].add(val)
        return True


if __name__ == "__main__":
    s = Solution()

    valid_board = [
        ["5", "3", ".", ".", "7", ".", ".", ".", "."],
        ["6", ".", ".", "1", "9", "5", ".", ".", "."],
        [".", "9", "8", ".", ".", ".", ".", "6", "."],
        ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
        ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
        ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
        [".", "6", ".", ".", ".", ".", "2", "8", "."],
        [".", ".", ".", "4", "1", "9", ".", ".", "5"],
        [".", ".", ".", ".", "8", ".", ".", "7", "9"],
    ]
    assert s.isValidSudoku(valid_board) is True

    invalid_board = [row[:] for row in valid_board]
    invalid_board[0][1] = "5"  # duplicate 5 in row 0
    assert s.isValidSudoku(invalid_board) is False

    print("All tests passed.")