33 posts tagged with "Array"

150. Evaluate Reverse Polish Notation - LeetCode

January 10, 2024 · One min read

from typing import Callable


class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        stack: list[int] = []
        operators: dict[str, Callable[[int, int], int]] = {
            '+': lambda a, b: a + b,
            '-': lambda a, b: a - b,
            '*': lambda a, b: a * b,
            '/': lambda a, b: int(a / b),
        }
        for token in tokens:
            if token in operators:
                b, a = stack.pop(), stack.pop()
                stack.append(operators[token](a, b))
            else:
                stack.append(int(token))
        return stack[0]

739. Daily Temperatures - LeetCode

January 10, 2024 · One min read

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        result = [0] * len(temperatures)
        stack = []
        for r in range(len(temperatures)):
            while stack and temperatures[stack[-1]] < temperatures[r]:  # l < r
                l = stack.pop()
                result[l] = r - l
            stack.append(r)
        return result

347. Top K Frequent Elements - LeetCode

January 3, 2024 · One min read

import heapq
from collections import Counter
from itertools import chain, islice


class Solution:  # O(n) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        buckets = [[] for _ in nums]
        for n, c in Counter(nums).items():
            buckets[-c].append(n)
        return list(islice(chain.from_iterable(buckets), k))


class Solution1:  # O(nlogn) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        heap = []
        for n, c in Counter(nums).items():
            heapq.heappush(heap, (-c, n))
        return [heapq.heappop(heap)[1] for _ in range(k)]


class Solution2:  # O(nlogn) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        heap = []
        for n, c in Counter(nums).items():
            heapq.heappush(heap, (-c, n))
        return [x[1] for x in heapq.nsmallest(k, heap)]


class Solution3:  # O(nlogn) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        return [n for n, _ in Counter(nums).most_common(k)]

49. Group Anagrams - LeetCode

January 2, 2024 · One min read

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        ht: dict[str, list[str]] = {}
        for s in strs:
            key = ''.join(sorted((s)))
            ht[key] = ht.get(key, [])
            ht[key].append(s)
        return list(ht.values())

213. House Robber II - LeetCode

September 22, 2023 · One min read

class Solution:
    def rob(self, nums: list[int]) -> int:
        def _rob(start: int, stop: int):
            a, b = 0, 0
            for i in range(start, stop):
                a, b = b, max(a + nums[i], b)
            return b

        return max(_rob(0, len(nums) - 1), _rob(1, len(nums)))

198. House Robber - LeetCode

September 21, 2023 · One min read

class Solution:
    def rob(self, nums: list[int]) -> int:
        a, b = 0, 0
        for n in nums:
            a, b = b, max(a + n, b)
        return b

189. Rotate Array - LeetCode

September 18, 2023 · One min read

class Solution1:
    def rotate(self, nums: list[int], k: int) -> None:
        if len(nums) > 1:
            k %= len(nums)
            nums[:-k], nums[-k:] = nums[-k:], nums[:-k]


class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        def reverse(start, stop):
            for i in range((stop - start) // 2):
                l, r = start + i, stop - 1 - i
                nums[l], nums[r] = nums[r], nums[l]

        k %= len(nums)
        reverse(0, len(nums) - k)
        reverse(len(nums) - k, len(nums))
        reverse(0, len(nums))

1282. Group the People Given the Group Size They Belong To - LeetCode

September 17, 2023 · One min read

class Solution:
    def groupThePeople(self, groupSizes: list[int]) -> list[list[int]]:
        ht: dict[int, list[int]] = {}
        for i, s in enumerate(groupSizes):
            ht[s] = ht.get(s, [])
            ht[s].append(i)
        result = []
        for s, l in ht.items():
            result.extend([l[i : i + s] for i in range(0, len(l), s)])
        return result

2798. Number of Employees Who Met the Target - LeetCode

September 6, 2023 · One min read

class Solution:
    def numberOfEmployeesWhoMetTarget(self, hours: list[int], target: int) -> int:
        return sum(1 for x in hours if x >= target)

2799. Count Complete Subarrays in an Array - LeetCode

September 6, 2023 · One min read

class Solution:
    def countCompleteSubarrays(self, nums: list[int]) -> int:
        amt, D, result, i = {}, len(set(nums)), 0, 0
        for num in nums:
            amt[num] = amt.get(num, 0) + 1
            while len(amt) == D:
                amt[nums[i]] -= 1
                if amt[nums[i]] == 0:
                    del amt[nums[i]]
                i += 1
            result += i
        return result

2807. Insert Greatest Common Divisors in Linked List - LeetCode

September 6, 2023 · One min read

from ..notes import gcd


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def insertGreatestCommonDivisors(self, head: ListNode) -> ListNode:
        node = head
        while node.next:
            node.next = ListNode(val=gcd(node.val, node.next.val), next=node.next)
            node = node.next.next
        return head

2815. Max Pair Sum in an Array - LeetCode

September 6, 2023 · One min read

class Solution:
    def maxSum(self, nums: list[int]) -> int:
        ht: dict[int, list[int]] = {}
        result = -1
        for num in nums:
            tmp, max_digit = num, 0
            while tmp:
                tmp, max_digit = tmp // 10, max(max_digit, tmp % 10)
            ht[max_digit] = sorted(ht.get(max_digit, []) + [num])[-2:]
            if len(ht[max_digit]) == 2:
                result = max(result, sum(ht[max_digit]))
        return result

322. Coin Change - LeetCode

September 5, 2023 · One min read

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [0] + [0xFFFFFFFF] * (amount)
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return (dp[-1], -1)[dp[-1] == 0xFFFFFFFF]

11. Container With Most Water - LeetCode

September 4, 2023 · One min read

class Solution:
    def maxArea(self, height: list[int]) -> int:
        result = 0
        l, r = 0, len(height) - 1
        while l != r:
            result = max(result, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return result

15. 3Sum - LeetCode

September 4, 2023 · One min read

class Solution:
    def threeSum(self, nums: list[int]):
        result = set()
        zero, neg, pos = counters = {}, {}, {}
        for num in nums:
            counter = counters[(num > 0) + (num != 0)]
            counter[num] = counter.get(num, 0) + 1
        # 0,0,0
        if zero.get(0, 0) >= 3:
            result.add((0, 0, 0))
        # -,+,?
        for n in neg:
            for p in pos:
                target: int = -(n + p)
                counter = counters[(target > 0) + (target != 0)]
                if target in counter:
                    triplet = tuple(sorted([n, p, target]))
                    if target in (n, p):  # duplicate
                        if counter[target] >= 2:
                            result.add(triplet)
                    else:
                        result.add(triplet)
        return result

33. Search in Rotated Sorted Array - LeetCode

August 31, 2023 · One min read

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums)
        target_is_rotated = target < nums[0]
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            mid_is_rotated = nums[mid] < nums[0]
            if (mid_is_rotated, target_is_rotated) == (True, False):  # [t] [m]
                hi = mid
            elif (mid_is_rotated, target_is_rotated) == (False, True):  # [m] [t]
                lo = mid + 1
            # same side
            elif nums[mid] > target:
                hi = mid
            else:
                lo = mid + 1
        return -1


class Solution1:
    def search(self, nums: list[int], target: int) -> int:
        # https://leetcode.com/problems/search-in-rotated-sorted-array/solutions/14435/clever-idea-making-it-simple/
        lo, hi = 0, len(nums)
        target_is_rotated = target < nums[0]
        inf = (-1) ** target_is_rotated * float('inf')
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            mid_is_rotated = nums[mid] < nums[0]
            if (nums[mid], inf)[mid_is_rotated != target_is_rotated] > target:
                hi = mid
            else:
                lo = mid + 1
        return -1

153. Find Minimum in Rotated Sorted Array - LeetCode

August 13, 2023 · One min read

class Solution:
    def findMin(self, nums: list[int]) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] <= nums[-1]:
                hi = mid
            else:
                lo = mid + 1
        return nums[lo]

53. Maximum Subarray - LeetCode

August 12, 2023 · One min read

class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        result = acc = nums[0]
        for i in range(1, len(nums)):
            acc = max(nums[i], nums[i] + acc)
            result = max(result, acc)
        return result

152. Maximum Product Subarray - LeetCode

August 12, 2023 · One min read

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        result = acc_max = acc_min = nums[0]
        for i in range(1, len(nums)):
            cand = nums[i], nums[i] * acc_max, nums[i] * acc_min
            acc_max, acc_min = max(cand), min(cand)
            result = max(result, acc_max, acc_min)
        return result

238. Product of Array Except Self - LeetCode

August 11, 2023 · One min read

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        result = [1] * len(nums)
        l = r = 1
        for i in range(len(nums)):
            result[i] *= l
            l *= nums[i]
            result[-1 - i] *= r
            r *= nums[-1 - i]
        return result

74. Search a 2D Matrix - LeetCode

August 9, 2023 · One min read

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        M, N = len(matrix), len(matrix[0])
        lo, hi = 0, M * N
        while lo < hi:
            mid = (lo + hi) // 2
            row, col = divmod(mid, N)
            if matrix[row][col] == target:
                return True
            if matrix[row][col] > target:
                hi = mid
            else:
                lo = mid + 1
        return False


class Solution1:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        M, N = len(matrix), len(matrix[0])
        lo, hi = 0, M
        while lo < hi:
            mid = (lo + hi) // 2
            if matrix[mid][0] == target:
                return True
            if matrix[mid][0] > target:
                hi = mid
            else:
                lo = mid + 1
        row = matrix[lo - 1]
        lo, hi = 0, N
        while lo < hi:
            mid = (lo + hi) // 2
            if row[mid] == target:
                return True
            if row[mid] > target:
                hi = mid
            else:
                lo = mid + 1
        return False

300. Longest Increasing Subsequence - LeetCode

July 26, 2023 · One min read

from bisect import bisect_left


class SolutionDp:  # O(n*n) / O(n)
    def lengthOfLIS(self, nums: list[int]) -> int:
        result, dp = 1, [1] * len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
                    result = max(result, dp[i])
        return result


class SolutionBs:  # O(n*log(n)) / O(n)
    def lengthOfLIS(self, nums: list[int]) -> int:
        result, dp = 0, [0] * len(nums)
        for num in nums:
            lo = bisect_left(dp, num, hi=result)
            result, dp[lo] = max(result, lo + 1), num
        return result


class SolutionBsLessSpace:  # O(n*log(n)) / O(n)
    def lengthOfLIS(self, nums: list[int]) -> int:
        result, dp = 0, []
        for i in range(len(nums)):
            if dp and nums[i] <= dp[-1]:
                dp[bisect_left(dp, nums[i])] = nums[i]
            else:
                result += 1
                dp.append(nums[i])
        return result


class SolutionBsInPlace:  # O(n*log(n)) / O(1)
    def lengthOfLIS(self, nums: list[int]) -> int:
        result = 0
        for i in range(len(nums)):
            lo = bisect_left(nums, nums[i], hi=result)
            result, nums[lo] = max(result, lo + 1), nums[i]
        return result

735. Asteroid Collision - LeetCode

July 21, 2023 · One min read

class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        s: list[int] = []
        for a in asteroids:
            s.append(a)
            while len(s) > 1 and s[-2] > 0 > s[-1]:
                if s[-2] == -s[-1]:
                    s.pop()
                elif s[-2] < -s[-1]:
                    s[-2] = s[-1]
                s.pop()
        return s

1146. Snapshot Array - LeetCode

June 14, 2023 · One min read

class SnapshotArray:
    def __init__(self, length: int):
        self._array: list[list[tuple[int, int]]] = [[(-1, 0)] for _ in range(length)]
        self._snap_id = -1

    def set(self, index: int, val: int) -> None:
        self._array[index].append((self._snap_id, val))

    def snap(self) -> int:
        self._snap_id += 1
        return self._snap_id

    @staticmethod
    def bs_r(a, t):
        l, r = 0, len(a)
        while l < r:
            m = (l + r) // 2
            if a[m] > t:
                r = m
            else:
                l = m + 1
        return l

    def get(self, index: int, snap_id: int) -> int:
        low = self.bs_r(self._array[index], (snap_id,))
        return self._array[index][low - 1][1]

1091. Shortest Path in Binary Matrix - LeetCode

June 3, 2023 · One min read

from collections import deque
from heapq import heappop, heappush
from itertools import product
from sys import maxsize

cellT = tuple[int, int]
countT = int


class Solution1:
    # [BFS] Runtime 1349 ms Beats 5.1%
    def shortestPathBinaryMatrix(self, grid: list[list[int]]):
        cellsT = set[cellT]

        N = len(grid)
        dummy_start_cell = (-1, -1)
        bottom_right_cell = (N - 1, N - 1)

        def find_adjacents(curr_row: int, curr_col: int):
            def is_valid(cand_cell: cellT):
                cand_row, cand_col = cand_cell
                return (
                    0 <= cand_row < N
                    and 0 <= cand_col < N
                    and grid[cand_row][cand_col] == 0
                )

            cand_cells = (
                (curr_row + row_offset, curr_col + col_offset)
                for row_offset, col_offset in product(range(-1, 2), repeat=2)
            )
            return filter(is_valid, cand_cells)

        queue: deque[cellsT] = deque([{dummy_start_cell}])
        visiteds: cellsT = set()
        count: countT = 1
        while queue:
            next_: cellsT = set()
            q: cellsT = queue.popleft()
            for cell in q:
                visiteds.add(cell)
                for adjacent in find_adjacents(*cell):
                    if adjacent in visiteds:
                        continue
                    if adjacent == bottom_right_cell:
                        return count
                    next_.add(adjacent)
            if next_:
                queue.append(next_)
            count += 1
        return -1


class Solution2:
    # [dijkstra] Runtime 995 ms Beats 6.89%
    def shortestPathBinaryMatrix(self, grid: list[list[int]]):
        N = len(grid)
        dummy_start_cell = (-1, -1)
        bottom_right_cell = (N - 1, N - 1)

        def find_adjacents(curr_row: int, curr_col: int):
            def is_valid(cand_cell: cellT):
                cand_row, cand_col = cand_cell
                return (
                    0 <= cand_row < N
                    and 0 <= cand_col < N
                    and grid[cand_row][cand_col] == 0
                )

            cand_cells = (
                (curr_row + row_offset, curr_col + col_offset)
                for row_offset, col_offset in product(range(-1, 2), repeat=2)
            )
            return filter(is_valid, cand_cells)

        heap: list[tuple[countT, cellT]] = [(0, dummy_start_cell)]
        visiteds: set[cellT] = set()
        while heap:
            cost, vertex = heappop(heap)
            if vertex == bottom_right_cell:
                return cost
            for new_vertex in find_adjacents(*vertex):
                if new_vertex in visiteds:
                    continue
                visiteds.add(new_vertex)
                new_cost = cost + 1
                heappush(heap, (new_cost, new_vertex))
        return -1


class Solution3:
    # [A*] Runtime 513 ms Beats 97.17%
    def shortestPathBinaryMatrix(self, grid: list[list[int]]):
        N = len(grid)
        dummy_start_cell = (-1, -1)
        bottom_right_cell = (N - 1, N - 1)

        def find_adjacents(curr_row: int, curr_col: int):
            def is_valid(cand_cell: cellT):
                cand_row, cand_col = cand_cell
                return (
                    0 <= cand_row < N
                    and 0 <= cand_col < N
                    and grid[cand_row][cand_col] == 0
                )

            cand_cells = (
                (curr_row + row_offset, curr_col + col_offset)
                for row_offset, col_offset in product(range(-1, 2), repeat=2)
            )
            return filter(is_valid, cand_cells)

        def heuristic(cell_row: int, cell_col: int):
            return max(abs(N - 1 - cell_row), abs(N - cell_col))

        heap: list[tuple[countT, countT, cellT]] = [(-maxsize, 0, dummy_start_cell)]
        costs: dict[cellT, countT] = {}
        while heap:
            estimate, cost, vertex = heappop(heap)
            if vertex == bottom_right_cell:
                return cost
            for new_vertex in find_adjacents(*vertex):
                new_cost = cost + 1
                if costs.get(new_vertex, maxsize) > new_cost:
                    costs[new_vertex] = new_cost
                    new_estimate = new_cost + heuristic(*new_vertex)
                    heappush(heap, (new_estimate, new_cost, new_vertex))
        return -1

1822. Sign of the Product of an Array - LeetCode

May 2, 2023 · One min read

class Solution:
    def arraySign(self, nums: list[int]) -> int:
        sig = True
        for num in nums:
            if num == 0:
                return 0
            if num < 0:
                sig = not sig
        return int(sig or -1)

983. Minimum Cost For Tickets - LeetCode

April 28, 2023 · One min read

class Solution:
    def mincostTickets(self, days: list[int], costs: list[int]) -> int:
        day_costs = dict(zip([1, 7, 30], costs))
        N = days[-1]
        dp = [0] * (N + 1)
        travel = set(days)
        for i in range(1, N + 1):
            if i in travel:
                dp[i] = min(dp[max(0, i - d)] + c for d, c in day_costs.items())
            else:
                dp[i] = dp[i - 1]
        return dp[-1]

54. Spiral Matrix - LeetCode

March 13, 2023 · One min read

class Solution:
    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
        if not matrix or not matrix[0]:
            return []
        result = []
        t, b, l, r = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
        while t <= b and l <= r:
            result.extend([matrix[t][x] for x in range(l, r + 1)])
            result.extend([matrix[x][r] for x in range(t + 1, b + 1)])
            if t < b and l < r:
                result.extend([matrix[b][x] for x in range(r - 1, l, -1)])
                result.extend([matrix[x][l] for x in range(b, t, -1)])
            t, b, l, r = t + 1, b - 1, l + 1, r - 1
        return result

1706. Where Will the Ball Fall - LeetCode

March 13, 2023 · One min read

class Solution:
    def findBall(self, grid: list[list[int]]) -> list[int]:
        N = len(grid[0])

        def drop(pos: int) -> int:
            for row in grid:
                adj = pos + row[pos]
                if not 0 <= adj < N:
                    return -1
                if row[pos] != row[adj]:
                    return -1
                pos = adj
            return pos

        return [drop(x) for x in range(N)]

78. Subsets - LeetCode

March 10, 2023 · One min read

class Solution:
    def subsets(self, nums: list[int]):
        result = [[]]
        for num in nums:
            result += [r + [num] for r in result]
        return result

1046. Last Stone Weight - LeetCode

January 27, 2023 · One min read

import heapq


class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        stones.append(0)
        stones = list(map(lambda x: -x, stones))
        heapq.heapify(stones)
        while len(stones) > 1:
            y, x = -heapq.heappop(stones), -heapq.heappop(stones)
            if x != y:
                heapq.heappush(stones, -(y - x))
        return -heapq.heappop(stones)

26. Remove Duplicates from Sorted Array - LeetCode

November 12, 2022 · One min read

class Solution1:
    def removeDuplicates(self, nums: list[int]) -> int:
        v, p = -101, 0  # ng
        for i in range(len(nums)):
            if nums[i] > v:
                v = nums[p] = nums[i]
                p += 1
        return p


class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        p = 1
        for i in range(1, len(nums)):
            if nums[p - 1] < nums[i]:
                nums[p], p = nums[i], p + 1
        return p

121. Best Time to Buy and Sell Stock - LeetCode

November 10, 2022 · One min read

class Solution:
    def maxProfit(self, prices) -> int:
        result, buy = 0, prices[0]
        for p in prices:
            result, buy = max(result, p - buy), min(buy, p)
        return result