DSA interview questions

def first_item(items):           # O(1): one step, whatever the size
    return items[0]

def total(items):                # O(n): one pass
    result = 0
    for x in items:
        result += x
    return result

def has_duplicate_pair(items):   # O(n²): every pair, with O(1) extra space
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def has_duplicate(items):        # O(n) time, but O(n) extra space for the set
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

print(has_duplicate_pair([3, 1, 4, 1]), has_duplicate([3, 1, 4, 1]))   # True True

import math

def is_prime(n):
    if n < 2:
        return False
    if n < 4:
        return True                       # 2 and 3
    if n % 2 == 0:
        return False
    for d in range(3, math.isqrt(n) + 1, 2):   # odd divisors up to √n
        if n % d == 0:
            return False
    return True

print([n for n in range(30) if is_prime(n)])   # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
print(is_prime(97), is_prime(91))              # True False: 91 = 7 × 13
print(is_prime(25), is_prime(-7))              # False False

import math

def primes_up_to(limit):
    is_p = [True] * (limit + 1)
    is_p[0:2] = [False, False]                    # 0 and 1 aren't prime
    for i in range(2, math.isqrt(limit) + 1):
        if is_p[i]:
            for multiple in range(i * i, limit + 1, i):
                is_p[multiple] = False            # a multiple of i can't be prime
    return [i for i, prime in enumerate(is_p) if prime]

print(primes_up_to(50))   # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def reverse_number(n):
    sign = -1 if n < 0 else 1
    n = abs(n)
    result = 0
    while n > 0:
        digit = n % 10                 # the last digit
        result = result * 10 + digit   # shift left and append it
        n //= 10                       # drop the last digit
    return sign * result

print(reverse_number(12345))   # 54321
print(reverse_number(-120))    # -21
print(reverse_number(0))       # 0

def is_palindrome_number(n):
    return n >= 0 and reverse_number(n) == n

def digit_sum(n):
    n, total = abs(n), 0
    while n:
        total += n % 10
        n //= 10
    return total

def is_armstrong(n):                  # 153 = 1³ + 5³ + 3³
    power = len(str(n))
    total, m = 0, n
    while m:
        total += (m % 10) ** power
        m //= 10
    return total == n

print(is_palindrome_number(121), is_palindrome_number(123))   # True False
print(digit_sum(9875))                                         # 29
print([n for n in range(1, 1000) if is_armstrong(n)])
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407]

def top_two(nums):
    if not nums:
        raise ValueError("empty array")
    first = second = float("-inf")
    for x in nums:
        if x > first:
            first, second = x, first      # the old first becomes second
        elif first > x > second:          # strictly between: skips copies of first
            second = x
    return first, (second if second != float("-inf") else None)

print(top_two([12, 35, 1, 10, 34, 1]))   # (35, 34)
print(top_two([5, 5, 3]))                # (5, 3)
print(top_two([7, 7]))                   # (7, None): no second distinct value
print(top_two([-4, -9]))                 # (-4, -9)

import heapq

print(heapq.nlargest(3, [12, 35, 1, 10, 34, 1]))   # [35, 34, 12]

def missing_number(nums):
    n = len(nums) + 1                     # one number is missing
    return n * (n + 1) // 2 - sum(nums)

def missing_number_xor(nums):
    n = len(nums) + 1
    result = 0
    for i in range(1, n + 1):
        result ^= i                       # every number that should be there
    for v in nums:
        result ^= v                       # every number that is there
    return result                         # pairs cancel; the missing one is left

print(missing_number([1, 2, 4, 5, 6]))       # 3
print(missing_number_xor([1, 2, 4, 5, 6]))   # 3
print(missing_number([2]))                   # 1
print(missing_number([1, 2, 3]))             # 4: the missing number can be n itself

def max_subarray_sum(nums):
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)    # extend the subarray, or restart at x
        best = max(best, current)
    return best

print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # 6: [4, -1, 2, 1]
print(max_subarray_sum([-3, -1, -2]))                       # -1

def max_subarray(nums):
    best = current = nums[0]
    start = best_start = best_end = 0
    for i in range(1, len(nums)):
        if current + nums[i] < nums[i]:
            current, start = nums[i], i          # restart here
        else:
            current += nums[i]
        if current > best:
            best, best_start, best_end = current, start, i
    return best, nums[best_start:best_end + 1]

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # (6, [4, -1, 2, 1])

def max_profit(prices):
    lowest, profit = float("inf"), 0
    for price in prices:
        lowest = min(lowest, price)
        profit = max(profit, price - lowest)
    return profit

print(max_profit([7, 1, 5, 3, 6, 4]))   # 5: buy at 1, sell at 6
print(max_profit([7, 6, 4, 3, 1]))      # 0: prices only fall, so don't trade

def reverse(nums, lo, hi):
    while lo < hi:
        nums[lo], nums[hi] = nums[hi], nums[lo]
        lo, hi = lo + 1, hi - 1

def rotate_right(nums, k):
    n = len(nums)
    if n == 0:
        return nums
    k %= n
    reverse(nums, 0, n - 1)    # [7, 6, 5, 4, 3, 2, 1]
    reverse(nums, 0, k - 1)    # [5, 6, 7, 4, 3, 2, 1]
    reverse(nums, k, n - 1)    # [5, 6, 7, 1, 2, 3, 4]
    return nums

print(rotate_right([1, 2, 3, 4, 5, 6, 7], 3))    # [5, 6, 7, 1, 2, 3, 4]
print(rotate_right([1, 2, 3], 4))                # [3, 1, 2]: 4 % 3 = 1
print(rotate_right([1, 2, 3], -1))               # [2, 3, 1]: same as rotating left by 1

def rotated(nums, k):
    if not nums:
        return []
    k %= len(nums)
    return nums[-k:] + nums[:-k]

print(rotated([1, 2, 3, 4, 5, 6, 7], 3))   # [5, 6, 7, 1, 2, 3, 4]

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

def is_palindrome_sentence(s):              # ignore case, spaces and punctuation
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left, right = left + 1, right - 1
    return True

print(is_palindrome("racecar"), is_palindrome("chai"))           # True False
print(is_palindrome(""), is_palindrome("a"))                     # True True
print(is_palindrome_sentence("A man, a plan, a canal: Panama"))  # True

def reverse_string(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left, right = left + 1, right - 1
    return "".join(chars)

print(reverse_string("Pune"))   # enuP

from collections import Counter

def is_anagram(a, b):
    return len(a) == len(b) and Counter(a) == Counter(b)

def is_anagram_counts(a, b):              # lowercase a-z, without Counter
    if len(a) != len(b):
        return False
    counts = [0] * 26
    for ch_a, ch_b in zip(a, b):
        counts[ord(ch_a) - ord("a")] += 1
        counts[ord(ch_b) - ord("a")] -= 1
    return all(c == 0 for c in counts)    # every letter balanced out

print(is_anagram("listen", "silent"), is_anagram("chai", "chat"))   # True False
print(is_anagram_counts("anagram", "nagaram"))                       # True
print(sorted("listen") == sorted("silent"))                          # True

def letters(s):
    return sorted(ch.lower() for ch in s if ch.isalnum())

print(letters("Dormitory") == letters("Dirty room"))   # True

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        groups["".join(sorted(word))].append(word)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

def reverse_words(s):
    return " ".join(reversed(s.split()))

print(repr(reverse_words("  the sky   is blue ")))   # 'blue is sky the'

def reverse_words_manual(s):
    words, i = [], len(s) - 1
    while i >= 0:
        while i >= 0 and s[i] == " ":     # skip spaces
            i -= 1
        end = i
        while i >= 0 and s[i] != " ":     # walk back to the start of the word
            i -= 1
        if end >= 0:
            words.append(s[i + 1:end + 1])
    return " ".join(words)

print(repr(reverse_words_manual("  the sky   is blue ")))   # 'blue is sky the'

def reverse_words_in_place(chars):
    def reverse(lo, hi):
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            lo, hi = lo + 1, hi - 1

    reverse(0, len(chars) - 1)            # 'eulb si yks eht'
    start = 0
    for i in range(len(chars) + 1):
        if i == len(chars) or chars[i] == " ":
            reverse(start, i - 1)         # turn each word back round
            start = i + 1
    return chars

print("".join(reverse_words_in_place(list("the sky is blue"))))   # blue is sky the

def two_sum(nums, target):
    seen = {}                             # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i                       # store after checking
    return None

print(two_sum([2, 7, 11, 15], 9))   # (0, 1)
print(two_sum([3, 3], 6))           # (0, 1)
print(two_sum([3, 4], 6))           # None: one 3 can't be used twice

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return left, right
        if total < target:
            left += 1                     # need a bigger sum
        else:
            right -= 1                    # need a smaller sum
    return None

print(two_sum_sorted([1, 3, 4, 6, 9], 10))   # (0, 4): 1 + 9
print(two_sum_sorted([1, 3, 4, 6, 9], 2))    # None

from collections import Counter

def first_unique(s):
    counts = Counter(s)
    for i, ch in enumerate(s):            # the string's order, not the map's
        if counts[ch] == 1:
            return i, ch
    return None

print(first_unique("swiss"))      # (1, 'w')
print(first_unique("aabb"))       # None
print(first_unique("chai"))       # (0, 'c')

def first_unique_plain(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    for i, ch in enumerate(s):
        if counts[ch] == 1:
            return i
    return -1

print(first_unique_plain("leetcode"))   # 0
print(first_unique_plain("loveleetcode"))   # 2

class ChainedHashMap:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0

    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value            # existing key: update it
                return
        bucket.append([key, value])        # new key: add it to this bucket's chain
        self.size += 1
        if self.size / len(self.buckets) > 0.75:   # load factor too high
            self._resize()

    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default

    def _resize(self):
        pairs = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(len(self.buckets) * 2)]
        self.size = 0
        for k, v in pairs:
            self.put(k, v)                 # every key goes to a new bucket

cities = ["Pune", "Delhi", "Chennai", "Mumbai", "Kochi", "Indore", "Surat"]
table = ChainedHashMap()
for i, city in enumerate(cities):
    table.put(city, i)
print(table.get("Kochi"), table.get("Goa"), len(table.buckets))   # 4 None 16

def sort_colours(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1                     # mid stays: the new nums[mid] is unchecked
    return nums

print(sort_colours([2, 0, 2, 1, 1, 0]))   # [0, 0, 1, 1, 2, 2]
print(sort_colours([2, 2, 0]))            # [0, 2, 2]
print(sort_colours([]))                   # []

def move_zeroes(nums):
    write = 0                             # where the next non-zero goes
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

print(move_zeroes([0, 1, 0, 3, 12]))   # [1, 3, 12, 0, 0]

def longest_unique_substring(s):
    last_seen = {}
    left = best = best_start = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:   # a repeat inside the window
            left = last_seen[ch] + 1
        last_seen[ch] = right
        if right - left + 1 > best:
            best, best_start = right - left + 1, left
    return best, s[best_start:best_start + best]

print(longest_unique_substring("abcabcbb"))   # (3, 'abc')
print(longest_unique_substring("pwwkew"))     # (3, 'wke')
print(longest_unique_substring("bbbbb"))      # (1, 'b')
print(longest_unique_substring("abba"))       # (2, 'ab')
print(longest_unique_substring(""))           # (0, '')

def binary_search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            low = mid + 1                 # it can only be to the right
        else:
            high = mid - 1                # it can only be to the left
    return -1

nums = [3, 8, 15, 21, 34, 55, 89]
print(binary_search(nums, 34))   # 4
print(binary_search(nums, 10))   # -1
print(binary_search([], 5))      # -1

def first_position(nums, target):
    low, high, answer = 0, len(nums) - 1, -1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            answer = mid
            high = mid - 1                # keep looking further left
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return answer

def last_position(nums, target):
    low, high, answer = 0, len(nums) - 1, -1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            answer = mid
            low = mid + 1                 # keep looking further right
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return answer

print(first_position([1, 2, 2, 2, 3], 2), last_position([1, 2, 2, 2, 3], 2))   # 1 3

from bisect import bisect_left, bisect_right

nums = [1, 2, 2, 2, 3]
print(bisect_left(nums, 2), bisect_right(nums, 2) - 1)   # 1 3

def bubble_sort(nums):
    n = len(nums)
    for end in range(n - 1, 0, -1):       # the last unsorted position
        swapped = False
        for i in range(end):
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                swapped = True
        if not swapped:                   # nothing moved: already sorted
            break
    return nums

print(bubble_sort([5, 1, 4, 2, 8]))   # [1, 2, 4, 5, 8]
print(bubble_sort([1, 2, 3]))         # [1, 2, 3]: one pass, no swaps, stop

def selection_sort(nums):
    n = len(nums)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):         # find the smallest in the unsorted part
            if nums[j] < nums[smallest]:
                smallest = j
        nums[i], nums[smallest] = nums[smallest], nums[i]
    return nums

def insertion_sort(nums):
    for i in range(1, len(nums)):
        current, j = nums[i], i - 1
        while j >= 0 and nums[j] > current:
            nums[j + 1] = nums[j]         # shift bigger items one place right
            j -= 1
        nums[j + 1] = current             # drop current into the gap
    return nums

print(selection_sort([64, 25, 12, 22, 11]))   # [11, 12, 22, 25, 64]
print(insertion_sort([12, 11, 13, 5, 6]))     # [5, 6, 11, 12, 13]

import math

def linear_search(nums, target):
    for i, x in enumerate(nums):
        if x == target:
            return i
    return -1

print(linear_search([7, 3, 9, 1], 9))   # 2

for n in (10, 1_000, 1_000_000, 1_000_000_000):
    print(f"{n:>13,} items: linear up to {n:,} checks, binary up to {math.floor(math.log2(n)) + 1}")

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left, right = merge_sort(nums[:mid]), merge_sort(nums[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:           # <= keeps equal items in order: stable
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    return merged + left[i:] + right[j:]

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # [3, 9, 10, 27, 38, 43, 82]

def partition(nums, low, high):
    pivot = nums[high]                    # Lomuto scheme: last element as pivot
    i = low
    for j in range(low, high):
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[high] = nums[high], nums[i]
    return i                              # the pivot's final position

def quick_sort(nums, low=0, high=None):
    if high is None:
        high = len(nums) - 1
    if low < high:
        p = partition(nums, low, high)
        quick_sort(nums, low, p - 1)
        quick_sort(nums, p + 1, high)
    return nums

print(quick_sort([10, 7, 8, 9, 1, 5]))   # [1, 5, 7, 8, 9, 10]

records = [("Asha", 85), ("Ravi", 72), ("Priya", 85), ("Arjun", 72)]
print(sorted(records, key=lambda r: r[1]))
# [('Ravi', 72), ('Arjun', 72), ('Asha', 85), ('Priya', 85)]

def search_rotated(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        if nums[low] <= nums[mid]:                    # left half is sorted
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:                                         # right half is sorted
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1

nums = [15, 18, 22, 3, 6, 9, 12]
print(search_rotated(nums, 6))    # 4
print(search_rotated(nums, 18))   # 1
print(search_rotated(nums, 7))    # -1
print(search_rotated([1], 1))     # 0

def find_min(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        if nums[mid] > nums[high]:
            low = mid + 1                 # the drop is to the right of mid
        else:
            high = mid                    # mid could be the minimum
    return nums[low]

print(find_min([15, 18, 22, 3, 6, 9, 12]))   # 3
print(find_min([1, 2, 3]))                    # 1: not rotated at all

def merge_intervals(intervals):
    merged = []
    for start, end in sorted(intervals):            # by start, then by end
        if merged and start <= merged[-1][1]:       # overlaps the last one
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1, 3], [8, 10], [2, 6], [15, 18]]))   # [[1, 6], [8, 10], [15, 18]]
print(merge_intervals([[1, 4], [4, 5]]))                      # [[1, 5]]: touching counts here
print(merge_intervals([[1, 10], [2, 3]]))                     # [[1, 10]]: max() keeps the longer end
print(merge_intervals([]))                                     # []

import heapq

def min_meeting_rooms(meetings):
    ends = []                                       # end times of rooms in use
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)            # reuse the room that freed up first
        else:
            heapq.heappush(ends, end)               # open a new room
    return len(ends)

print(min_meeting_rooms([[0, 30], [5, 10], [15, 20]]))   # 2
print(min_meeting_rooms([[7, 10], [2, 4]]))              # 1

def factorial(n):
    if n <= 1:                         # base case: answered directly
        return 1
    return n * factorial(n - 1)        # recursive case: a smaller problem

print(factorial(5))   # 120

def forever(n):
    return forever(n + 1)              # no base case

try:
    forever(0)
except RecursionError as error:
    print(error)                       # maximum recursion depth exceeded

def permutations(s):
    result = []

    def backtrack(path, remaining):
        if not remaining:                  # every character placed
            result.append(path)
            return
        for i in range(len(remaining)):
            backtrack(path + remaining[i], remaining[:i] + remaining[i + 1:])

    backtrack("", s)
    return result

print(permutations("abc"))   # ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
print(len(permutations("abcd")))   # 24 = 4!

def permute_unique(s):
    chars, out = list(s), []

    def backtrack(start):
        if start == len(chars):
            out.append("".join(chars))
            return
        tried = set()
        for i in range(start, len(chars)):
            if chars[i] in tried:             # this letter was already tried here
                continue
            tried.add(chars[i])
            chars[start], chars[i] = chars[i], chars[start]   # choose
            backtrack(start + 1)                              # explore
            chars[start], chars[i] = chars[i], chars[start]   # undo

    backtrack(0)
    return out

print(permute_unique("aab"))   # ['aab', 'aba', 'baa']

def subsets(nums):
    result = []

    def backtrack(i, current):
        if i == len(nums):
            result.append(current[:])     # copy: current keeps changing
            return
        current.append(nums[i])           # include nums[i]
        backtrack(i + 1, current)
        current.pop()                     # exclude nums[i]
        backtrack(i + 1, current)

    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

def subsets_iterative(nums):
    result = [[]]
    for x in nums:
        result += [subset + [x] for subset in result]
    return result

print(subsets_iterative([1, 2, 3]))
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

def subsets_bitmask(nums):
    n = len(nums)
    return [[nums[j] for j in range(n) if mask >> j & 1] for mask in range(1 << n)]

print(subsets_bitmask([1, 2, 3]))
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

from collections import deque

stack = []
stack.append("a")
stack.append("b")
stack.append("c")
print(stack.pop())       # c: last in, first out
print(stack[-1])         # b: peek without removing

queue = deque()
queue.append("a")
queue.append("b")
queue.append("c")
print(queue.popleft())   # a: first in, first out

class QueueWithStacks:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def enqueue(self, x):
        self.inbox.append(x)

    def dequeue(self):
        if not self.outbox:                  # refill only when empty
            while self.inbox:
                self.outbox.append(self.inbox.pop())   # reverses the order
        return self.outbox.pop()

q = QueueWithStacks()
for x in (1, 2, 3):
    q.enqueue(x)
print(q.dequeue(), q.dequeue())   # 1 2
q.enqueue(4)
print(q.dequeue(), q.dequeue())   # 3 4

def is_balanced(expr):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in expr:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False              # nothing to close, or the wrong kind
    return not stack                      # leftovers were never closed

print(is_balanced("{[()()]}"))       # True
print(is_balanced("([)]"))           # False: closed in the wrong order
print(is_balanced("(("))             # False: never closed
print(is_balanced("a * (b + c)]"))   # False: nothing to close
print(is_balanced(""))               # True

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                                # indices waiting for an answer
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x           # x is the first bigger value to their right
        stack.append(i)
    return result

print(next_greater([4, 5, 2, 25]))     # [5, 25, 25, -1]
print(next_greater([13, 7, 6, 12]))    # [-1, 12, 12, -1]
print(next_greater([5, 4, 3]))         # [-1, -1, -1]

def daily_temperatures(temps):
    wait = [0] * len(temps)
    stack = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            wait[j] = i - j
        stack.append(i)
    return wait

print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))   # [1, 1, 4, 2, 1, 1, 0, 0]

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def to_list(head):
    values = []
    while head:
        values.append(head.value)
        head = head.next
    return values

head = Node(1, Node(2, Node(3)))          # 1 -> 2 -> 3

def insert_after(node, value):            # O(1): only two pointers change
    node.next = Node(value, node.next)

insert_after(head, 99)
print(to_list(head))                      # [1, 99, 2, 3]

nums = [1, 2, 3]
nums.insert(1, 99)                        # O(n): 2 and 3 shift right
print(nums)                               # [1, 99, 2, 3]

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def build(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

def reverse_list(head):
    prev, current = None, head
    while current:
        nxt = current.next          # 1. save the rest of the list
        current.next = prev         # 2. turn this node's pointer around
        prev, current = current, nxt   # 3. step forward
    return prev                     # the old tail is the new head

print(to_list(reverse_list(build([1, 2, 3, 4]))))   # [4, 3, 2, 1]
print(to_list(reverse_list(build([7]))))            # [7]
print(to_list(reverse_list(None)))                  # []

def reverse_recursive(head):
    if head is None or head.next is None:
        return head                       # an empty or one-node list is its own reverse
    new_head = reverse_recursive(head.next)
    head.next.next = head                 # the next node now points back here
    head.next = None
    return new_head

print(to_list(reverse_recursive(build([1, 2, 3]))))   # [3, 2, 1]

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:              # the same node object, not just equal values
            return True
    return False

nodes = [Node(i) for i in range(5)]
for a, b in zip(nodes, nodes[1:]):
    a.next = b                        # 0 -> 1 -> 2 -> 3 -> 4
print(has_cycle(nodes[0]))            # False
nodes[4].next = nodes[2]              # 4 points back to 2: a loop
print(has_cycle(nodes[0]))            # True

def loop_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow
    return None

print(loop_start(nodes[0]).value)   # 2

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow                       # fast reached the end; slow is halfway

letters = [Node(ch) for ch in "abcde"]
for a, b in zip(letters, letters[1:]):
    a.next = b
print(middle(letters[0]).value)       # c

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

#        1
#       / \
#      2   3
#     / \
#    4   5
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))

def preorder(node, out):
    if node:
        out.append(node.value)            # root first
        preorder(node.left, out)
        preorder(node.right, out)
    return out

def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.value)            # root in the middle
        inorder(node.right, out)
    return out

def postorder(node, out):
    if node:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.value)            # root last
    return out

print(preorder(root, []))    # [1, 2, 4, 5, 3]
print(inorder(root, []))     # [4, 2, 5, 1, 3]
print(postorder(root, []))   # [4, 5, 2, 3, 1]

from collections import deque

def level_order(root):
    if not root:
        return []
    levels, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):       # everything queued now is one level
            node = queue.popleft()
            level.append(node.value)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels

print(level_order(root))   # [[1], [2, 3], [4, 5]]

def inorder_iterative(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                       # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.value)
        node = node.right                 # then handle the right subtree
    return out

print(inorder_iterative(root))   # [4, 2, 5, 1, 3]

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = self.right = None

def insert(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)   # this version sends duplicates right
    return root

def contains(root, value):
    while root and root.value != value:
        root = root.left if value < root.value else root.right   # one path down
    return root is not None

def inorder(node):
    return inorder(node.left) + [node.value] + inorder(node.right) if node else []

def height(node):
    return 0 if node is None else 1 + max(height(node.left), height(node.right))

root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, v)
print(inorder(root))                       # [20, 30, 40, 50, 60, 70, 80]: sorted
print(contains(root, 60), contains(root, 65))   # True False
print(height(root))                        # 3: balanced, about log₂ 7

chain = None
for v in [10, 20, 30, 40, 50, 60, 70]:     # sorted input
    chain = insert(chain, v)
print(height(chain))                       # 7: every node only has a right child

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def height(node):
    if node is None:
        return 0                          # empty tree
    return 1 + max(height(node.left), height(node.right))

root = TreeNode(1, TreeNode(2, TreeNode(4, TreeNode(8))), TreeNode(3))
print(height(root))          # 4: nodes on the longest path, 1 -> 2 -> 4 -> 8
print(height(root) - 1)      # 3: edges on that path
print(height(None))          # 0

from collections import deque

def height_iterative(root):
    if not root:
        return 0
    depth, queue = 0, deque([root])
    while queue:
        depth += 1
        for _ in range(len(queue)):       # one full level per pass
            node = queue.popleft()
            queue.extend(child for child in (node.left, node.right) if child)
    return depth

print(height_iterative(root))   # 4

def is_balanced(root):
    def check(node):                      # the height, or -1 if unbalanced
        if node is None:
            return 0
        left, right = check(node.left), check(node.right)
        if left == -1 or right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)
    return check(root) != -1

print(is_balanced(root))                                    # False: node 2's sides differ by 2
print(is_balanced(TreeNode(1, TreeNode(2), TreeNode(3))))   # True

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def is_valid_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return True
    if not low < node.value < high:
        return False
    return (is_valid_bst(node.left, low, node.value) and      # left: below this value
            is_valid_bst(node.right, node.value, high))       # right: above it

good = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(10))

#        10
#       /  \
#      5    15
#          /  \
#         6    20       6 is in 10's right subtree, but smaller than 10
tricky = TreeNode(10, TreeNode(5), TreeNode(15, TreeNode(6), TreeNode(20)))

print(is_valid_bst(good))     # True
print(is_valid_bst(tricky))   # False

def children_only_check(node):            # the tempting but wrong version
    if node is None:
        return True
    if node.left and node.left.value >= node.value:
        return False
    if node.right and node.right.value <= node.value:
        return False
    return children_only_check(node.left) and children_only_check(node.right)

print(children_only_check(tricky))   # True: fooled, because 6 < 15 is all it checks

def is_valid_bst_inorder(root):
    previous = float("-inf")
    stack, node = [], root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if node.value <= previous:        # must be strictly increasing
            return False
        previous = node.value
        node = node.right
    return True

print(is_valid_bst_inorder(good), is_valid_bst_inorder(tricky))   # True False

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def lca(root, p, q):
    if root is None or root is p or root is q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:              # p and q were found on different sides
        return root
    return left or right            # both on one side, or neither found

#          3
#        /   \
#       5     1
#      / \   / \
#     6   2 0   8
#        / \
#       7   4
n7, n4 = TreeNode(7), TreeNode(4)
n2 = TreeNode(2, n7, n4)
n5 = TreeNode(5, TreeNode(6), n2)
n1 = TreeNode(1, TreeNode(0), TreeNode(8))
root = TreeNode(3, n5, n1)

print(lca(root, n5, n1).value)   # 3
print(lca(root, n7, n4).value)   # 2
print(lca(root, n5, n4).value)   # 5: a node counts as its own ancestor

def insert(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def lca_bst(root, a, b):
    while root:
        if a < root.value and b < root.value:
            root = root.left
        elif a > root.value and b > root.value:
            root = root.right
        else:
            return root             # the paths to a and b split here
    return None

bst = None
for v in [6, 2, 8, 0, 4, 7, 9, 3, 5]:
    bst = insert(bst, v)
print(lca_bst(bst, 2, 8).value, lca_bst(bst, 2, 4).value, lca_bst(bst, 3, 5).value)   # 6 2 4

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": [],
}

def bfs(start):
    order, visited, queue = [], {start}, deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)          # mark when queued, so nothing is queued twice
                queue.append(nxt)
    return order

def dfs(node, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(node)
    order.append(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(nxt, visited, order)
    return order

print(bfs("A"))   # ['A', 'B', 'C', 'D', 'E', 'F']: level by level
print(dfs("A"))   # ['A', 'B', 'D', 'E', 'F', 'C']: deep first, then back up

def shortest_path(start, goal):
    parent, queue = {start: None}, deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return None

print(shortest_path("A", "F"))   # ['A', 'C', 'F']: 2 edges, not 3 via B and E

def count_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen = set()

    def flood(r, c):
        stack = [(r, c)]                  # iterative DFS: no recursion limit
        seen.add((r, c))
        while stack:
            r, c = stack.pop()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and grid[nr][nc] == "1" and (nr, nc) not in seen):
                    seen.add((nr, nc))
                    stack.append((nr, nc))

    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                islands += 1              # a new island
                flood(r, c)               # mark all of it
    return islands

grid = [
    "11000",
    "11000",
    "00100",
    "00011",
]
print(count_islands(grid))                 # 3
print(count_islands(["111", "010", "111"]))   # 1: all connected through the middle
print(count_islands(["000"]))              # 0

def fib_recursive(n):                     # O(2^n): recomputes everything
    if n < 2:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

def fib_memo(n, memo=None):               # top-down: O(n) time and space
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

def fib_bottom_up(n):                     # bottom-up: O(n) time, O(1) space
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_recursive(20), fib_memo(20), fib_bottom_up(20))   # 6765 6765 6765
print(fib_bottom_up(90))                                     # 2880067194370816120
print([fib_bottom_up(i) for i in range(10)])                 # the series: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

calls = 0

def fib_counted(n):
    global calls
    calls += 1
    return n if n < 2 else fib_counted(n - 1) + fib_counted(n - 2)

fib_counted(25)
print(calls)   # 242785 calls to compute fib(25)

def climb_stairs(n):
    a, b = 1, 1                           # ways to reach step 0 and step 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

print([climb_stairs(n) for n in range(1, 8)])   # [1, 2, 3, 5, 8, 13, 21]

def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1     # use coin c on top of the best way to make a - c
    return dp[amount] if dp[amount] != INF else -1

def greedy_change(coins, amount):          # the tempting but wrong approach
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count if amount == 0 else -1

print(coin_change([1, 3, 4], 6), greedy_change([1, 3, 4], 6))   # 2 3
print(coin_change([1, 2, 5], 11))                                # 3: 5 + 5 + 1
print(coin_change([2], 3))                                       # -1: impossible
print(coin_change([1], 0))                                       # 0

def count_ways(coins, amount):
    ways = [1] + [0] * amount             # one way to make 0: no coins
    for c in coins:                       # coins in the outer loop: each combination counted once
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

print(count_ways([1, 2, 5], 5))   # 4: 5, 2+2+1, 2+1+1+1, 1+1+1+1+1

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1          # extend the match
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])   # drop a character

    # Walk back from the corner to recover one of the longest subsequences
    out, i, j = [], m, n
    while i and j:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], "".join(reversed(out))

print(lcs("ABCBDAB", "BDCABA"))   # (4, 'BCBA')
print(lcs("AGGTAB", "GXTXAYB"))   # (4, 'GTAB')
print(lcs("abc", "xyz"))          # (0, '')

def lcs_length(a, b):
    if len(a) < len(b):
        a, b = b, a                       # keep the shorter string across the row
    previous = [0] * (len(b) + 1)
    for ch in a:
        current = [0]
        for j, other in enumerate(b, 1):
            if ch == other:
                current.append(previous[j - 1] + 1)
            else:
                current.append(max(previous[j], current[j - 1]))
        previous = current
    return previous[-1]

print(lcs_length("ABCBDAB", "BDCABA"))   # 4