8 posts tagged with "Binary Search"

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

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]

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

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

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]

class Solution:  # O(n) / O(n)
    # https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271/C++Python-Sliding-Window-O(N)-instead-of-O(26N)/
    def characterReplacement(self, s: str, k: int) -> int:
        c = {}  # counter
        mf = 0  # max_freq
        i = 0
        for j, char in enumerate(s):
            c[char] = c.get(char, 0) + 1
            mf = max(mf, c[char])
            if not ((j - i + 1) - mf <= k):  # shift right
                c[s[i]] -= 1
                i += 1
        return len(s) - i  # length


class Solution2:  # O(n) / O(n)
    # https://leetcode.com/problems/longest-repeating-character-replacement/solutions/278271/C++Python-Sliding-Window-O(N)-instead-of-O(26N)/
    def characterReplacement(self, s: str, k: int) -> int:
        c = {}
        mf, i = 0, 0
        for j, char in enumerate(s):
            c[char] = c.get(char, 0) + 1
            mf = max(mf, c[char])
            if i - mf >= k:
                c[s[j - i]] -= 1
            else:
                i += 1  # update when more
        return i


class SolutionBS:  # O(log(n)) / O(n)
    # TODO: review
    # https://leetcode.com/problems/longest-repeating-character-replacement/solutions/2805777
    def characterReplacement(self, s: str, k: int) -> int:
        def too_long(length: int):
            c = {}
            mf, i = 0, 0
            for j, char in enumerate(s):
                c[char] = c.get(char, 0) + 1
                mf = max(mf, c[char])
                if length - mf <= k:
                    return False
                if j - i + 1 > length:
                    c[s[i]] -= 1
                    i += 1
            return True

        l, r = 0, len(s)
        while l < r:
            m = (l + r) // 2
            l, r = (l, m) if too_long(length=m + 1) else (m + 1, r)
        return (l - 1) + 1

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
def guess(num: int) -> int:
    ...


class Solution:
    def guessNumber(self, n: int) -> int:
        l, r = 0, n
        while l < r:
            m = (l + r) // 2
            if not guess(m):
                return m
            l, r = (l, m) if guess(m) < 0 else (m + 1, r)
        return l

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            l, r = (l, m) if nums[m] > target else (m + 1, r)
        return -1