Constraints

• 1 <= len(s) <= 10^5
• s contains digits, spaces, and the operators +, -, *, /
• The expression is valid and all intermediate results fit in a signed 32-bit integer

Examples

Solution

def solution(s):
    total = 0
    last = 0
    num = 0
    op = '+'
    n = len(s)

    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)

        if (not ch.isdigit() and ch != ' ') or i == n - 1:
            if op == '+':
                total += last
                last = num
            elif op == '-':
                total += last
                last = -num
            elif op == '*':
                last = last * num
            elif op == '/':
                if last < 0:
                    last = -((-last) // num)
                else:
                    last = last // num

            op = ch
            num = 0

    return total + last

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

Hints

1. When you reach a new operator, you have finished reading the previous number.
2. Keep a running total for completed + and - terms, and a separate last term for * and / precedence.

Constraints

• 0 <= len(nums) <= 2000
• 1 <= nums[i] <= 10^4
• An O(n^2) solution after sorting is expected

Examples

Solution

def solution(nums):
    nums = sorted(nums)
    n = len(nums)
    count = 0

    for k in range(n - 1, 1, -1):
        left = 0
        right = k - 1

        while left < right:
            if nums[left] + nums[right] > nums[k]:
                count += right - left
                right -= 1
            else:
                left += 1

    return count

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

Hints

1. After sorting, if nums[i] + nums[j] > nums[k], then every index from i to j - 1 paired with j will also work for that k.
2. Try fixing the largest side first and use two pointers for the other two sides.

Constraints

• 0 <= len(intervals) <= 10^5
• -10^9 <= l <= r <= 10^9
• Intervals are closed and merging should include endpoint touching

Examples

Solution

def solution(intervals):
    if not intervals:
        return []

    intervals = sorted(intervals, key=lambda interval: (interval[0], interval[1]))
    merged = [intervals[0][:]]

    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:
            if end > last[1]:
                last[1] = end
        else:
            merged.append([start, end])

    return merged

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

Hints

1. Sorting by interval start lets you process intervals from left to right.
2. Compare each interval only with the last merged interval.

Constraints

• 0 <= m, n <= 300
• grid[r][c] is either '1' or '0'
• An O(m * n) traversal is expected

Examples

Solution

def solution(grid):
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    clusters = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and not visited[r][c]:
                clusters += 1
                stack = [(r, c)]
                visited[r][c] = True

                while stack:
                    cr, cc = stack.pop()
                    for dr, dc in directions:
                        nr, nc = cr + dr, cc + dc
                        if 0 <= nr < rows and 0 <= nc < cols:
                            if grid[nr][nc] == '1' and not visited[nr][nc]:
                                visited[nr][nc] = True
                                stack.append((nr, nc))

    return clusters

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

Hints

1. Every time you find an unvisited land cell, start a DFS or BFS and mark the whole component.
2. Be careful not to count the same land cell more than once.

Constraints

• 0 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• A linear-time, constant-extra-space solution is expected

Examples

Solution

def solution(nums):
    n = len(nums)
    i = 0

    while i < n:
        curr = nums[i]
        correct_index = curr - 1

        if 1 <= curr <= n and nums[i] != nums[correct_index]:
            nums[i], nums[correct_index] = nums[correct_index], nums[i]
        else:
            i += 1

    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    return n + 1

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

Hints

1. If the array length is n, the answer must be in the range 1 to n + 1.
2. Try placing each value x in index x - 1 whenever 1 <= x <= n.

Constraints

• 1 <= len(nums) <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9
• An O(n) solution is expected

Examples

Solution

def solution(nums):\n    if not nums:\n        return (0, -1, -1)\n\n    max_sum = nums[0]\n    current_sum = nums[0]\n    best_start = 0\n    best_end = 0\n    current_start = 0\n\n    for i in range(1, len(nums)):\n        if current_sum + nums[i] < nums[i]:\n            current_sum = nums[i]\n            current_start = i\n        else:\n            current_sum += nums[i]\n\n        if current_sum > max_sum:\n            max_sum = current_sum\n            best_start = current_start\n            best_end = i\n        elif current_sum == max_sum:\n            if current_start < best_start or (current_start == best_start and i < best_end):\n                best_start = current_start\n                best_end = i\n\n    return (max_sum, best_start, best_end)

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

Hints

1. For each position, decide whether it is better to extend the current subarray or start a new one there.
2. Track the start index whenever you reset the running sum.

Constraints

• 0 <= len(prices) <= 2 * 10^5
• 0 <= prices[i] <= 10^9
• An O(n) one-pass solution is expected

Examples

Solution

def solution(prices):
    if isinstance(prices, tuple) and len(prices) == 1:
        prices = prices[0]

    min_price = float('inf')
    best = 0

    for price in prices:
        if price < min_price:
            min_price = price
        else:
            profit = price - min_price
            if profit > best:
                best = profit

    return best

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

Hints

1. As you scan left to right, remember the lowest price seen so far.
2. At each day, ask what profit you would make if you sold today.

Constraints

• 0 <= len(nums) <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9
• An average O(n) solution is expected

Examples

Solution

def solution(nums):
    values = set(nums)
    best = 0

    for x in values:
        if x - 1 not in values:
            current = x
            length = 1

            while current + 1 in values:
                current += 1
                length += 1

            if length > best:
                best = length

    return best

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

Hints

1. A number starts a sequence only if the previous number is not present.
2. Using a set lets you check whether neighbors exist in average O(1) time.

Constraints

• 1 <= numCourses <= 10^5
• 0 <= len(prerequisites) <= 10^5
• 0 <= a, b < numCourses

Examples

Solution

def solution(numCourses, prerequisites):
    import heapq

    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    heap = [i for i in range(numCourses) if indegree[i] == 0]
    heapq.heapify(heap)

    order = []

    while heap:
        current = heapq.heappop(heap)
        order.append(current)

        for neighbor in graph[current]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                heapq.heappush(heap, neighbor)

    if len(order) == numCourses:
        return (True, order)
    return (False, [])

Time complexity: O((numCourses + len(prerequisites)) log numCourses). Space complexity: O(numCourses + len(prerequisites)).

Hints

1. Think of courses as a directed graph and prerequisites as edges.
2. If you repeatedly remove zero-indegree nodes and cannot process all nodes, a cycle exists.