Constraints

• 0 <= len(arr) <= 200000
• -10^9 <= arr[i], target <= 10^9

Examples

Solution

def solution(target, arr):
    greater = sum(1 for x in arr if x > target)
    smaller = sum(1 for x in arr if x < target)
    if greater > smaller:
        return 'greater'
    if smaller > greater:
        return 'smaller'
    return 'tie'

Time complexity: O(n). Space complexity: O(1).

Hints

1. You only need two counters while scanning the array once.
2. Elements equal to target should not affect either counter.

Constraints

• 0 <= initial_state <= 7
• 1 <= month <= 12
• The date is valid in a non-leap year

Examples

Solution

def solution(initial_state, month, day):
    month_lengths = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    offset = sum(month_lengths[:month - 1]) + day - 1
    return (initial_state + offset) % 8

Time complexity: O(1). Space complexity: O(1).

Hints

1. First compute how many days have passed since January 1.
2. Use modulo 8 after adding the day offset.

Constraints

• The matrix dimensions are valid for all commands
• Row indices in commands always refer to the current matrix shape
• 0 <= total number of cells <= 10^5

Examples

Solution

def solution(grid, commands):
    grid = [row[:] for row in grid]
    for command in commands:
        parts = command.split()
        if parts[0] == 'reverseRow':
            r = int(parts[1])
            grid[r].reverse()
        elif parts[0] == 'swap':
            r1 = int(parts[1])
            r2 = int(parts[2])
            grid[r1], grid[r2] = grid[r2], grid[r1]
        elif parts[0] == 'rotate':
            if not grid:
                grid = []
            else:
                grid = [list(row) for row in zip(*grid[::-1])]
    return grid

Time complexity: O(total work done by commands). Space complexity: O(number of cells) for rotation output.

Hints

1. For a clockwise rotation, the new rows come from columns of the old matrix scanned bottom to top.
2. Remember that rotate changes the number of rows and columns.

Constraints

• 0 <= len(nums) <= 200000
• -10^9 <= nums[i] <= 10^9

Examples

Solution

def solution(nums):
    lengths = {}
    seen = set()
    best = 0
    ans = []

    for x in nums:
        if x not in seen:
            seen.add(x)
            left = lengths.get(x - 1, 0)
            right = lengths.get(x + 1, 0)
            cur = left + 1 + right
            lengths[x] = cur
            lengths[x - left] = cur
            lengths[x + right] = cur
            if cur > best:
                best = cur
        ans.append(best)

    return ans

Time complexity: O(n) average. Space complexity: O(n).

Hints

1. Duplicate values do not change the seen set.
2. Store the length of each consecutive interval at its boundaries.

Constraints

• 0 <= len(numbers) <= 200000
• 0 <= numbers[i], target <= 10^9

Examples

Solution

def solution(numbers, target):
    from collections import Counter

    counts = Counter(str(x) for x in numbers)
    t = str(target)
    ans = 0

    for k in range(1, len(t)):
        left = t[:k]
        right = t[k:]
        if left not in counts or right not in counts:
            continue
        if left == right:
            ans += counts[left] * (counts[left] - 1)
        else:
            ans += counts[left] * counts[right]

    return ans

Time complexity: O(n + L). Space complexity: O(n).

Hints

1. Work with string forms of the numbers.
2. Try every split of the target string into a prefix and suffix.

Constraints

• 1 <= number of rows, columns <= 500
• The grid contains at least one digit
• All rows have the same length

Examples

Solution

def solution(grid):
    if not grid:
        return 0

    n = len(grid)
    m = len(grid[0])
    NEG = -10**18

    digit_dp = [[NEG] * m for _ in range(n)]
    plus_dp = [[NEG] * m for _ in range(n)]
    minus_dp = [[NEG] * m for _ in range(n)]
    best = NEG

    def best_incoming_digit(i, j):
        res = NEG
        if i > 0 and digit_dp[i - 1][j] > res:
            res = digit_dp[i - 1][j]
        if j > 0 and digit_dp[i][j - 1] > res:
            res = digit_dp[i][j - 1]
        return res

    for i in range(n):
        for j in range(m):
            c = grid[i][j]
            if c.isdigit():
                val = ord(c) - ord('0')
                cur = val

                if i > 0:
                    if plus_dp[i - 1][j] != NEG:
                        cur = max(cur, plus_dp[i - 1][j] + val)
                    if minus_dp[i - 1][j] != NEG:
                        cur = max(cur, minus_dp[i - 1][j] - val)
                if j > 0:
                    if plus_dp[i][j - 1] != NEG:
                        cur = max(cur, plus_dp[i][j - 1] + val)
                    if minus_dp[i][j - 1] != NEG:
                        cur = max(cur, minus_dp[i][j - 1] - val)

                digit_dp[i][j] = cur
                if cur > best:
                    best = cur

            elif c == '+':
                incoming = best_incoming_digit(i, j)
                if incoming != NEG:
                    plus_dp[i][j] = incoming
            else:
                incoming = best_incoming_digit(i, j)
                if incoming != NEG:
                    minus_dp[i][j] = incoming

    return best if best != NEG else 0

Time complexity: O(nm). Space complexity: O(nm).

Hints

1. A valid path must alternate between digit cells and operator cells.
2. For each cell, track the best complete value if the path ends at a digit, and the best pending value if the path ends at + or -.

Constraints

• 0 <= len(nums) <= 200000
• 0 <= nums[i] <= 10^9

Examples

Solution

def solution(nums):
    ans = 0
    stack = []

    for x in nums:
        while stack and stack[-1] > x:
            stack.pop()
        prev = stack[-1] if stack else 0
        ans += x - prev
        stack.append(x)

    return ans

Time complexity: O(n). Space complexity: O(n).

Hints

1. You do not need to simulate every subtraction explicitly.
2. A monotonic nondecreasing stack can capture how much new contribution each element adds.

Constraints

• 1 <= maxWidth <= 100
• Each individual word length is at most maxWidth
• Total number of words across all blocks is at most 10^5

Examples

Solution

def solution(blocks, maxWidth):
    def justify(words, total_chars):
        spaces = maxWidth - total_chars
        if len(words) == 1:
            return words[0] + ' ' * spaces

        gaps = len(words) - 1
        base = spaces // gaps
        extra = spaces % gaps
        parts = []

        for i, word in enumerate(words[:-1]):
            parts.append(word)
            parts.append(' ' * (base + (1 if i < extra else 0)))
        parts.append(words[-1])
        return ''.join(parts)

    result = []

    for block in blocks:
        words = []
        for piece in block:
            words.extend(piece.split())

        if not words:
            continue

        current = []
        current_chars = 0

        for word in words:
            if not current:
                current = [word]
                current_chars = len(word)
            elif current_chars + len(current) + len(word) <= maxWidth:
                current.append(word)
                current_chars += len(word)
            else:
                result.append(justify(current, current_chars))
                current = [word]
                current_chars = len(word)

        result.append(justify(current, current_chars))

    return result

Time complexity: O(total characters in all words). Space complexity: O(number of words in the current line, excluding output).

Hints

1. First flatten each block into a word list by splitting on spaces.
2. To justify one line, compute total spaces needed, divide them across gaps, and place extra spaces from left to right.

Constraints

• 0 <= len(s) <= 200000
• s contains ASCII letters and spaces

Examples

Solution

def solution(s):
    s = s.lower()
    return sum(1 for i in range(len(s) - 2) if s[i] == s[i + 2])

Time complexity: O(n). Space complexity: O(n) due to lowercasing the string.

Hints

1. Scan every window of length 3 exactly once.
2. Convert the string to one case first so each comparison is simple.

Constraints

• 0 <= len(arr) <= 200000
• 1 <= rate <= 200000
• arr contains only 'A' and 'P'

Examples

Solution

def solution(arr, rate):
    n = len(arr)
    a_positions = [i for i, ch in enumerate(arr) if ch == 'A']
    rounds = 0

    while True:
        while a_positions and a_positions[-1] >= n:
            a_positions.pop()

        changed = False
        trailing_p = n - a_positions[-1] - 1 if a_positions else n

        if trailing_p >= rate:
            n -= rate
            changed = True
            while a_positions and a_positions[-1] >= n:
                a_positions.pop()

        if a_positions:
            a_positions.pop()
            changed = True

        if not changed:
            break

        rounds += 1

    return rounds

Time complexity: O(n + number of removals). Space complexity: O(number of A values).

Hints

1. You do not need to rebuild the array every round.
2. Track the current effective length and the positions of remaining 'A' characters.

Constraints

• 2 <= len(nums) <= 200000
• 1 <= distance < len(nums)
• -10^9 <= nums[i] <= 10^9

Examples

Solution

def solution(nums, distance):
    from collections import deque

    pairs = sorted((value, idx) for idx, value in enumerate(nums))

    def can(limit):
        min_q = deque()
        max_q = deque()
        left = 0

        for right, (value, idx) in enumerate(pairs):
            while min_q and min_q[-1][1] >= idx:
                min_q.pop()
            min_q.append((right, idx))

            while max_q and max_q[-1][1] <= idx:
                max_q.pop()
            max_q.append((right, idx))

            while value - pairs[left][0] > limit:
                if min_q and min_q[0][0] == left:
                    min_q.popleft()
                if max_q and max_q[0][0] == left:
                    max_q.popleft()
                left += 1

            if right > left:
                min_idx = min_q[0][1]
                max_idx = max_q[0][1]
                if idx - min_idx >= distance or max_idx - idx >= distance:
                    return True

        return False

    low = 0
    high = max(nums) - min(nums)

    while low < high:
        mid = (low + high) // 2
        if can(mid):
            high = mid
        else:
            low = mid + 1

    return low

Time complexity: O(n log n + n log V). Space complexity: O(n).

Hints

1. Sort by value and think about the smallest allowed value gap.
2. You can binary search the answer and check feasibility with a sliding window over sorted values.

Constraints

• 0 <= len(A) <= 200000
• -10^9 <= A[i] <= 10^9

Examples

Solution

def solution(A):
    if not A:
        return [[], []]

    values = sorted(set(A))
    index = {v: i + 1 for i, v in enumerate(values)}

    class Fenwick:
        def __init__(self, n):
            self.n = n
            self.bit = [0] * (n + 1)

        def add(self, i, delta):
            while i <= self.n:
                self.bit[i] += delta
                i += i & -i

        def query(self, i):
            s = 0
            while i > 0:
                s += self.bit[i]
                i -= i & -i
            return s

    bit_b = Fenwick(len(values))
    bit_c = Fenwick(len(values))
    B, C = [], []

    for a in A:
        idx = index[a]
        greater_b = len(B) - bit_b.query(idx)
        greater_c = len(C) - bit_c.query(idx)

        if greater_b > greater_c:
            B.append(a)
            bit_b.add(idx, 1)
        elif greater_b < greater_c:
            C.append(a)
            bit_c.add(idx, 1)
        else:
            if len(B) <= len(C):
                B.append(a)
                bit_b.add(idx, 1)
            else:
                C.append(a)
                bit_c.add(idx, 1)

    return [B, C]

Time complexity: O(n log n). Space complexity: O(n).

Hints

1. For each group, you need to know how many existing values are greater than the current one.
2. Coordinate compression plus two Fenwick trees can maintain those counts efficiently.