Python Syntax for DSA

a = [0] * 3
grid = [[0] * 3 for _ in range(2)]  # 2 rows x 3 cols, independent
grid[0][0] = 1
print(grid)                # [[1, 0, 0], [0, 0, 0]]
bad = [[0] * 3] * 2        # both rows are the same list object
bad[0][0] = 1
print(bad)                 # [[1, 0, 0], [1, 0, 0]]
print(a, len(grid), len(grid[0]))  # [0, 0, 0] 2 3

a = [1, 2, 3]
a.append(4)
a.insert(0, 0)
print(a)                # [0, 1, 2, 3, 4]
print(a.pop())          # 4
print(a.pop(0))         # 0
a.remove(2)
print(a, a[-1])         # [1, 3] 3
a.extend([7, 8])
print(a)                # [1, 3, 7, 8]

a = [0, 1, 2, 3, 4, 5]
print(a[1:4])          # [1, 2, 3]
print(a[:2], a[4:])    # [0, 1] [4, 5]
print(a[::2], a[-2:])  # [0, 2, 4] [4, 5]
print(a[::-1])         # [5, 4, 3, 2, 1, 0]
b = a[:]
b[0] = 99
print(a[0], b[0])      # 0 99
print(a[10:20])        # []

a = [4, 7, 4, 9]
print(len(a))           # 4
print(7 in a, 5 in a)   # True False
print(a.index(4))       # 0
print(a.count(4))       # 2
print(not [])           # True

names = ['ann', 'bob', 'cat']
scores = [90, 75, 88]
for i, n in enumerate(names, start=1):
    print(i, n, end=' ')            # 1 ann 2 bob 3 cat
print()
print(list(zip(names, scores)))     # [('ann', 90), ('bob', 75), ('cat', 88)]
print(list(zip([1, 2, 3], 'ab')))   # [(1, 'a'), (2, 'b')]
print(list(zip(*[[1, 2], [3, 4]]))) # [(1, 3), (2, 4)]

sq = [x * x for x in range(5)]
print(sq)                         # [0, 1, 4, 9, 16]
evens = [x for x in range(10) if x % 2 == 0]
print(evens)                      # [0, 2, 4, 6, 8]
flat = [v for row in [[1, 2], [3]] for v in row]
print(flat)                       # [1, 2, 3]
tags = ['even' if x % 2 == 0 else 'odd' for x in range(3)]
print(tags)                       # ['even', 'odd', 'even']

a = [3, -7, 5]
print(sum(a), min(a), max(a))     # 1 -7 5
print(max(a, key=abs))            # -7
print(min(['kiwi', 'fig', 'banana'], key=len))  # fig
print(max([], default=0))         # 0
print(any(x < 0 for x in a))      # True
print(all(x > 0 for x in a))      # False
print(all([]), any([]))           # True False

s = "python"
print(s[0], s[-1], len(s))   # p n 6
print(s[1:4])                # yth
print(s[::-1])               # nohtyp
print(''.join(reversed(s)))  # nohtyp
w = "level"
print(w == w[::-1])          # True

s = "abc"
chars = list(s)
chars[0] = 'z'
print(''.join(chars))        # zbc
parts = []
for i in range(4):
    parts.append(str(i))
print('-'.join(parts))       # 0-1-2-3
print(''.join(map(str, [1, 2, 3])))  # 123

line = "  the  quick brown "
print(line.split())               # ['the', 'quick', 'brown']
print("a,b,,c".split(','))        # ['a', 'b', '', 'c']
print(' '.join(['x', 'y', 'z']))  # x y z
print(line.strip() + '|')         # the  quick brown|
print("xxhixx".strip('x'))        # hi
print("a-b-c".replace('-', ''))   # abc

s = "banana"
print(s.find("an"), s.find("z"))   # 1 -1
print(s.index("na"))               # 2
print(s.count("a"), s.count("ana"))  # 3 1
print(s.startswith("ban"), s.endswith("na"))  # True True
print("nan" in s)                  # True

print("abc".isalpha(), "123".isdigit())    # True True
print("a1".isalnum(), " ".isspace())       # True True
print("Q".isupper(), "Hi".lower(), "hi".upper())  # True hi HI
s = "A man, a plan"
clean = [c.lower() for c in s if c.isalnum()]
print(''.join(clean))                      # amanaplan

print(ord('a'), chr(98))         # 97 b
counts = [0] * 26
for c in "abca":
    counts[ord(c) - ord('a')] += 1
print(counts[:3])                # [2, 1, 1]
print(chr(ord('a') + 25))        # z
print(tuple(counts) == tuple([2, 1, 1] + [0] * 23))  # True

name, score = "Ada", 9.5678
print(f"{name} scored {score:.2f}")   # Ada scored 9.57
n = 5
print(f"{n:03d} {n:b} {n=}")          # 005 101 n=5
print(f"[{'x':>3}]")                  # [  x]
print(f"{1234567:,}")                 # 1,234,567

d = {'a': 1}
d['b'] = 2
print(d.get('z'), d.get('z', 0))   # None 0
print('a' in d, len(d))            # True 2
d['a'] = d.get('a', 0) + 1
print(d)                           # {'a': 2, 'b': 2}
del d['b']
print(d.pop('a'), d)               # 2 {}

ages = {'ann': 30, 'bob': 25}
for k, v in ages.items():
    print(k, v, end='; ')          # ann 30; bob 25;
print()
print(list(ages), list(ages.values()))  # ['ann', 'bob'] [30, 25]
graph = {}
for u, v in [(1, 2), (1, 3), (2, 3)]:
    graph.setdefault(u, []).append(v)
print(graph)                       # {1: [2, 3], 2: [3]}

from collections import defaultdict
groups = defaultdict(list)
for w in ["eat", "tea", "tan", "ate"]:
    groups[''.join(sorted(w))].append(w)
print(dict(groups))   # {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}
cnt = defaultdict(int)
cnt['x'] += 1
print(cnt['x'], cnt['missing'], len(cnt))  # 1 0 2

from collections import Counter
c = Counter("mississippi")
print(c['s'], c['z'])              # 4 0
print(c.most_common(2))            # [('i', 4), ('s', 4)]
print(Counter("listen") == Counter("silent"))  # True
a, b = Counter("aabc"), Counter("abd")
print(a - b)                       # Counter({'a': 1, 'c': 1})
print(a & b, (a + b)['a'])         # Counter({'a': 1, 'b': 1}) 3
print(not (Counter("ab") - Counter("aabb")))  # True

nums = [3, 1, 3]
last = {v: i for i, v in enumerate(nums)}
print(last)                      # {3: 2, 1: 1}
sq = {x: x * x for x in range(3)}
print(sq)                        # {0: 0, 1: 1, 2: 4}
print(dict(zip("ab", [1, 2])))   # {'a': 1, 'b': 2}

freq = {'a': 3, 'b': 1, 'c': 2}
print(sorted(freq, key=freq.get))                    # ['b', 'c', 'a']
print(sorted(freq.items(), key=lambda kv: -kv[1]))   # [('a', 3), ('c', 2), ('b', 1)]
print(max(freq, key=freq.get))                       # a

s = set()
for x in [3, 1, 3]:
    s.add(x)
print(len(s), 3 in s)       # 2 True
s.discard(99)
s.remove(1)
print(s)                    # {3}
nums = [3, 1, 3, 2]
print(len(set(nums)) != len(nums))   # True
print(list(dict.fromkeys(nums)))     # [3, 1, 2]

a, b = {1, 2, 3}, {2, 3, 4}
print(a | b)          # {1, 2, 3, 4}
print(a & b)          # {2, 3}
print(a - b)          # {1}
print(a ^ b)          # {1, 4}
print({1, 2} <= a)    # True

visited = set()
visited.add((0, 1))
print((0, 1) in visited)            # True
state = [2, 3]
visited.add(tuple(state))
print(len(visited))                 # 2
groups = {frozenset("abc"): "g1"}
print(groups[frozenset("cba")])     # g1

import heapq
h = []
for x in [5, 1, 4]:
    heapq.heappush(h, x)
print(h[0])                        # 1
print(heapq.heappop(h))            # 1
print(heapq.heappop(h), len(h))    # 4 1

import heapq
a = [7, 2, 9, 1]
heapq.heapify(a)
print(a[0])                                        # 1
print([heapq.heappop(a) for _ in range(len(a))])   # [1, 2, 7, 9]

import heapq
nums = [3, 8, 5]
h = [-x for x in nums]
heapq.heapify(h)
print(-h[0])                # 8
heapq.heappush(h, -10)
print(-heapq.heappop(h))    # 10
print(-heapq.heappop(h))    # 8

import heapq
tasks = []
heapq.heappush(tasks, (2, "write"))
heapq.heappush(tasks, (1, "plan"))
heapq.heappush(tasks, (2, "test"))
while tasks:
    pri, name = heapq.heappop(tasks)
    print(pri, name, end=' | ')      # 1 plan | 2 test | 2 write |
print()

import heapq, itertools
h, counter = [], itertools.count()
for dist, node in [(1, {'id': 'A'}), (1, {'id': 'B'})]:
    heapq.heappush(h, (dist, next(counter), node))
print(heapq.heappop(h)[2])        # {'id': 'A'}
try:
    heapq.heappush(h, (1, {'id': 'C'}))
    heapq.heappush(h, (1, {'id': 'D'}))
except TypeError:
    print("dicts are not comparable")  # dicts are not comparable

import heapq
a = [5, 1, 9, 3, 7]
print(heapq.nlargest(2, a))      # [9, 7]
print(heapq.nsmallest(2, a))     # [1, 3]
pts = [(1, 2), (3, 0), (0, 1)]
print(heapq.nsmallest(1, pts, key=lambda p: p[0]**2 + p[1]**2))  # [(0, 1)]

import heapq
def kth_largest(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)
    return h[0]
print(kth_largest([3, 2, 1, 5, 6, 4], 2))   # 5

from collections import deque
q = deque([2, 3])
q.append(4)
q.appendleft(1)
print(q)                       # deque([1, 2, 3, 4])
print(q.popleft(), q.pop())    # 1 4
print(q[0], q[-1], len(q))     # 2 3 2
q.rotate(1)
print(list(q))                 # [3, 2]

from collections import deque
graph = {0: [1, 2], 1: [3], 2: [3], 3: []}
dist = {0: 0}
q = deque([0])
while q:
    u = q.popleft()
    for v in graph[u]:
        if v not in dist:
            dist[v] = dist[u] + 1
            q.append(v)
print(dist)                    # {0: 0, 1: 1, 2: 1, 3: 2}

def valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)
    return not stack
print(valid("([]{})"), valid("(]"), valid("(("))   # True False False

from collections import deque
def window_max(nums, k):
    dq, out = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k: dq.popleft()   # front left the window
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out
print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))  # [3, 3, 5, 5, 6, 7]

a = [3, 1, 2]
b = sorted(a)
print(a, b)                          # [3, 1, 2] [1, 2, 3]
r = a.sort()
print(a, r)                          # [1, 2, 3] None
print(sorted("bca", reverse=True))   # ['c', 'b', 'a']

ps = [("bo", 25), ("al", 30), ("cy", 25)]
print(sorted(ps, key=lambda p: p[1]))           # [('bo', 25), ('cy', 25), ('al', 30)]
print(sorted(ps, key=lambda p: (-p[1], p[0])))  # [('al', 30), ('bo', 25), ('cy', 25)]
words = ["bb", "a", "ccc", "dd"]
print(sorted(words, key=lambda w: (len(w), w))) # ['a', 'bb', 'dd', 'ccc']

from functools import cmp_to_key
def cmp(a, b):
    if a + b > b + a:
        return -1
    return 1 if a + b < b + a else 0
nums = [3, 30, 34, 5, 9]
s = sorted(map(str, nums), key=cmp_to_key(cmp))
print(''.join(s))              # 9534330

intervals = [[8, 10], [1, 3], [2, 6]]
intervals.sort(key=lambda x: x[0])
merged = []
for s, e in intervals:
    if merged and s <= merged[-1][1]:
        merged[-1][1] = max(merged[-1][1], e)
    else:
        merged.append([s, e])
print(merged)                  # [[1, 6], [8, 10]]

import bisect
a = [1, 2, 2, 2, 5]
print(bisect.bisect_left(a, 2))    # 1
print(bisect.bisect_right(a, 2))   # 4
print(bisect.bisect_right(a, 2) - bisect.bisect_left(a, 2))  # 3
i = bisect.bisect_left(a, 4)
print(i, i < len(a) and a[i] == 4) # 4 False

import bisect
a = [1, 4, 9]
bisect.insort(a, 5)
bisect.insort(a, 0)
print(a)                 # [0, 1, 4, 5, 9]

def first_true(lo, hi, ok):
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
print(first_true(0, 100, lambda x: x * x >= 50))   # 8
piles, h = [3, 6, 7, 11], 8
fits = lambda k: sum((p + k - 1) // k for p in piles) <= h
print(first_true(1, max(piles), fits))             # 4

from itertools import permutations, combinations, product
print(list(permutations([1, 2, 3], 2)))  # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
print(list(combinations('abc', 2)))      # [('a', 'b'), ('a', 'c'), ('b', 'c')]
print(list(product([0, 1], repeat=2)))   # [(0, 0), (0, 1), (1, 0), (1, 1)]
print(len(list(permutations(range(4)))))  # 24

from itertools import accumulate
a = [3, 1, 4, 1]
pre = list(accumulate(a, initial=0))
print(pre)                         # [0, 3, 4, 8, 9]
print(pre[3] - pre[1])             # 5
print(list(accumulate(a, max)))    # [3, 3, 4, 4]

from itertools import groupby
s = "aaabccdd"
print([(k, len(list(g))) for k, g in groupby(s)])  # [('a', 3), ('b', 1), ('c', 2), ('d', 2)]
print(''.join(f"{k}{len(list(g))}" for k, g in groupby(s)))  # a3b1c2d2

from functools import cache
@cache
def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)
print(ways(40))                  # 165580141
print(ways.cache_info().currsize)  # 41

from functools import reduce
import operator
print(reduce(operator.mul, [1, 2, 3, 4], 1))         # 24
print(reduce(lambda a, b: a ^ b, [4, 1, 2, 1, 2]))   # 4
print(reduce(operator.add, [], 0))                   # 0

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next
def build(vals):
    dummy = tail = ListNode()
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next
head = build([1, 2, 3])
print(head.val, head.next.val, head.next.next.next)   # 1 2 None

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right
#     1
#    / \
#   2   3
root = TreeNode(1, TreeNode(2), TreeNode(3))
def inorder(n):
    return inorder(n.left) + [n.val] + inorder(n.right) if n else []
def depth(n):
    return 1 + max(depth(n.left), depth(n.right)) if n else 0
print(inorder(root), depth(root))   # [2, 1, 3] 2

from dataclasses import dataclass
@dataclass(order=True)
class Job:
    end: int
    start: int
    name: str = ""
jobs = [Job(5, 1, "b"), Job(3, 0, "a")]
print(min(jobs))                  # Job(end=3, start=0, name='a')
print(sorted(jobs)[-1].name)      # b
print(Job(1, 0) == Job(1, 0))     # True

import heapq
class Node:
    def __init__(self, cost, name):
        self.cost, self.name = cost, name
    def __lt__(self, other):
        return self.cost < other.cost
h = []
for c, n in [(3, "c"), (1, "a"), (2, "b")]:
    heapq.heappush(h, Node(c, n))
print([heapq.heappop(h).name for _ in range(3)])   # ['a', 'b', 'c']

def add_bad(x, acc=[]):
    acc.append(x)
    return acc
print(add_bad(1), add_bad(2))      # [1, 2] [1, 2]
def add_ok(x, acc=None):
    acc = [] if acc is None else acc
    acc.append(x)
    return acc
print(add_ok(1), add_ok(2))        # [1] [2]

import math
best = float('inf')
for x in [7, 3, 9]:
    best = min(best, x)
print(best)                                 # 3
print(math.inf == float('inf'))             # True
print(-math.inf < -10**18)                  # True
print([math.inf] * 3)                       # [inf, inf, inf]

print(7 // 2, -7 // 2)        # 3 -4
print(-7 % 3, 7 % -3)         # 2 -2
print(int(-7 / 2))            # -3
print(divmod(17, 5))          # (3, 2)
print(4 / 2, -(-7 // 2))      # 2.0 4

import math
MOD = 10**9 + 7
print(pow(2, 10, 1000), pow(3, -1, 7))   # 24 5
print(pow(2, 100, MOD))                  # 976371285
print(math.gcd(12, 18), math.lcm(4, 6))  # 6 12
print(math.isqrt(17), math.comb(5, 2))   # 4 10
print(2**64)                             # 18446744073709551616

import sys
sys.setrecursionlimit(10**6)
def depth(n):
    return 0 if n == 0 else 1 + depth(n - 1)
print(depth(5000))               # 5000

import sys
input = sys.stdin.readline
# stdin:
# 3
# 1 2 3
n = int(input())
nums = list(map(int, input().split()))
print(n, sum(nums))             # 3 6

x = 12
print(bin(x), x & 1, x >> 1, x << 2)    # 0b1100 0 6 48
print(x & (x - 1), x & -x)              # 8 4
print(bin(x).count('1'), x.bit_count()) # 2 2
print(x > 0 and x & (x - 1) == 0)       # False
print(5 ^ 5, 5 ^ 0)                     # 0 5

a, b = 1, 2
a, b = b, a
print(a, b)                 # 2 1
nums = [5, 6, 7]
nums[0], nums[2] = nums[2], nums[0]
print(nums)                 # [7, 6, 5]
first, *rest = nums
print(first, rest)          # 7 [6, 5]

grid = [[1, 1, 0], [0, 1, 0]]
R, C = len(grid), len(grid[0])
r, c = 0, 1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
    nr, nc = r + dr, c + dc
    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
        print((nr, nc), end=' ')    # (1, 1) (0, 0)
print()