O(logN) , O(sort)

The Classic Binary Search Algorithm

704. Binary Search (Easy)

Solution

This is the standard template, which can be used to solve almost all binary search related problems.

This template is mentioned as Template 2 in LeetCode Binary Search Explore Card.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

def search(self, nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo if nums[lo] == target else -1

702. Search in a Sorted Array of Unknown Size (Medium)

Solution

This is also the standard binary search, but here we don’t know the length of the array.

Problem is split into two subproblems:

Analysis

Time Complexity: O(log****_T_**)**

where:

  • T is the index of target value

There are two operations here, and both take O(logT)

  • Find the lo, hi indices

  • Binary Search from found lo, hi indices

Space Complexity: O(1)

def search(self, reader: "ArrayReader", target: int) -> int:
    lo, hi = 0, 1
    # Find the boundary indices such that the target lies in-between (low, high)
    while target > reader.get(hi):
        lo = hi
        hi <<= 2
    # Typical binary search
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if reader.get(mid) < target:
            lo = mid + 1
        else:
            hi = mid
    return lo if reader.get(lo) == target else -1

74. Search a 2D Matrix (Medium)

Solution

Row-major 1D of the given matrix will be an normal 1D sorted array.

Analysis

Time Complexity: O(log****_MN_**)**

where:

  • M, N are #rows and #cols respectively

Space Complexity: O(1)

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    row, col = len(matrix), len(matrix[0])
    get = lambda i: matrix[i // col][
        i % col
    ]  # access an element of matrix using offset 'i'
    lo, hi = 0, row * col - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if get(mid) < target:
            lo = mid + 1
        else:
            hi = mid
    return get(lo) == target

Bisect Algorithms

Bisect Left

Problem

Return the position to insert a new element in the sorted array. If the element is already present in the array, return the leftmost position to insert.

Also, bisect_left is supposed to return the index of the leftmost target, which is 0 <= index < len(arr), if present, else if 0 when element is smaller than all element else if len(arr) when element greater than all elements.

Example 1:

arr = [1, 5, 5, 5, 10, 12]

Example 2:

arr = [1, 5, 5, 5, 10, 12]

Example 3:

arr = [1, 5, 5, 5, 10, 12]

Example 4:

arr = [1, 5, 5, 5, 10, 12]

Example 5:

arr = [1, 5, 5, 5, 10, 12]

Solution

Very similar to the authentic binary search algorithm seen here 704. Binary Search (Easy).

The differences are:

  • Check if the new element is greater than all elements, then return hi + 1 as the position.

  • Return index instead of boolean.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

    def bisect_left(self, arr, target, lo: int = 0, hi: int = None):
        # hi is exclusive. The insert position can never be >= len(arr)
        hi = (hi or len(arr)) - 1
        if lo == hi + 1:  # if array is empty
            return -1
        if arr[hi] < target:
            return hi + 1
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if arr[mid] < target:
                lo = mid + 1
            else:
                hi = mid
        return lo

Bisect Left Reverse (with descending elements)

def bisect_left_rev(self, arr, target, lo: int = 0, hi: int = None):
    # hi is exclusive. The insert position can never be >= len(arr)
    hi = (hi or len(arr)) - 1
    if lo == hi + 1:  # if array is empty
        return -1
    if arr[hi] > target:
        return hi + 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] > target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Bisect Right

Problem

Return the position to insert a new element in the sorted array. If the element is already present in the array, return the rightmost position to insert.

Also, bisect_right is supposed to return the index of the rightmost target, which is 0 <= index < len(arr), if present, else if 0 when smaller than all element else if len(arr) + 1 when greater than all elements.

Example 1:

arr = [1, 5, 5, 5, 10, 12]

Example 2:

arr = [1, 5, 5, 5, 10, 12]

Example 3:

arr = [1, 5, 5, 5, 10, 12]

Example 4:

arr = [1, 5, 5, 5, 10, 12]

Example 5:

arr = [1, 5, 5, 5, 10, 12]

Solution

Very similar to the authentic binary search algorithm seen here 704. Binary Search (Easy).

The differences are:

  • hi is inclusive since the answer can be the index to be returned in cases where target is greater than all elements.

  • We need to move lo by lo = mid + 1 even if arr[mid] == target, because we need to reach the rightmost element.

  • Return index instead of boolean.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

def bisect_right(self, arr, target, lo: int = 0, hi: int = None):
    # hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
    hi = hi or len(arr)
    if lo == hi:  # if array is empty
        return -1
    if arr[hi - 1] < target:
        return hi
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Bisect Right Reverse (with descending elements)

def bisect_right_rev(self, arr, target, lo: int = 0, hi: int = None):
    # hi is inclusive. The insert position of the new element can be at the end of the list with index=len(arr)
    hi = hi or len(arr)
    if lo == hi:  # if array is empty
        return -1
    if arr[hi - 1] > target:
        return hi
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] >= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Bisect Derivatives

744. Find Smallest Letter Greater Than Target (Easy)

Solution

Since duplicates are allowed, we need to glide through all duplicate targets and move to rightmost target. We can clearly use bisect_right() to get rightmost element.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

def nextGreatestLetter(self, letters: List[str], target: str) -> str:
    index = self.bisect_right(letters, target)
    return letters[index % len(letters)]

35. Search Insert Position (Easy)

Also

Solution

Since duplicates are not allowed, we need to return the leftmost/rightmost target. We can either use bisect_right() or bisect_left().

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

def searchInsert(self, nums: List[int], target: int) -> int:
    return self.bisect_left(nums, target)

362. Design Hit Counter (Medium)

Solution

Solution for this design problem is inspired from a solution comment.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

hit would be having O(1), and the array would always be sorted because the timestamp would be in chronological order (i.e., timestamp is monotonically increasing)

getHits would be having O(logN) since, it uses binary search

Space Complexity: O(N)

where:

N is the length of the array

class HitCounter:
    def __init__(self):
        self.hits = []

    def hit(self, timestamp: int) -> None:
        self.hits.append(timestamp)

    def getHits(self, timestamp: int) -> int:
        index = self.bisect_left(self.hits, timestamp - 300 + 1)
        return len(self.hits) - index if 0 <= index < len(self.hits) else 0

Bisect left & right

34. Find First and Last Position of Element in Sorted Array (Medium)

Solution

Two subproblems:

  • Find bisect_left : which points to first occurrence if target exists

  • Find bisect_right : which points one next to last occurrence if target exists

bisect_left is supposed to return the index of the leftmost target, which is 0 <= index < len(arr), if present, else if 0 when smaller than all element else if len(arr) + 1 when greater than all elements.

bisect_right is supposed to return the index of the rightmost target, which is 0 <= index < len(arr), if present, else if 0 when smaller than all element else if len(arr) + 1 when greater than all elements.

When the element is not in the list:

  • If target is smaller than all elements, then both left and right will be 0

  • If target is greater than all elements, then both left and right will be len(arr) + 1

  • If target is in the middle, both left and right will point to the same index (to which it is supposed to be inserted)

So, if the target is not present, left == right is always true.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Both bisect_left and bisect_right takes O(logN)

Space Complexity: O(1)

def searchRange(self, nums: List[int], target: int) -> List[int]:
    left = self.bisect_left(nums, target)
    right = self.bisect_right(nums, target)
    if not nums or left == right:  # left==right when the element is not present
        return [-1, -1]
    return [left, right - 1]

2089. Find Target Indices After Sorting Array (Easy)

Solution

Once array is sorted, solution is very similar to 34. Find First and Last Position of Element in Sorted Array (Medium), instead of returning [first, last] , return [first, ..., last].

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Both bisect_left and bisect_right takes O(logN)

Space Complexity: O(1)

def targetIndices(self, nums: List[int], target: int) -> List[int]:
    nums = sorted(nums)
    left = self.bisect_left(nums, target)
    right = self.bisect_right(nums, target)
    return list(range(left, right))

1150. Check If a Number Is Majority Element in a Sorted Array (Easy)

Also

Solution

Very similar to 34. Find First and Last Position of Element in Sorted Array (Medium), instead of returning [first, last] , check if the range has majority.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Both bisect_left and bisect_right takes O(logN)

Space Complexity: O(1)

def isMajorityElement(self, nums: List[int], target: int) -> bool:
    left = self.bisect_left(nums, target)
    right = self.bisect_right(nums, target)
    count = right - left
    return count > len(nums) / 2

Element Occurrence (E)

Solution

Very similar to 34. Find First and Last Position of Element in Sorted Array (Medium), instead of returning [first, last] , return the count = right - left.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Both bisect_left and bisect_right takes O(logN)

Space Complexity: O(1)

def findCount(nums: List[int], target: int):
    left = bisect_left(nums, target)
    right = bisect_right(nums, target)
    count = right - left
    return count if count != 0 else -1

Slight Variants

1064. Fixed Point (Easy)

Also

Solution

We need to return the smallest index satisfying the condition, which also means that the leftmost target is to be returned. This is a variant of sibling of bisect_left

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

def fixedPoint(self, arr: List[int]) -> int:
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < mid:
            lo = mid + 1
        else:
            hi = mid
    return lo if arr[lo] == lo else -1

374. Guess Number Higher or Lower (Easy)

Solution

Standard binary search template with minor change

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

def guessNumber(self, n: int) -> int:
    lo, hi = 0, n
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if guess(mid) == 1:  # 1 if guess is lower than the target
            lo = mid + 1
        else:  # -1 or 0 if guess is greater than or equal to the target
            hi = mid
    return lo

278. First Bad Version (Easy)

Solution

Standard binary search template with minor change

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

def firstBadVersion(self, n: int) -> int:
    lo, hi = 0, n
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if isBadVersion(mid) == False:
            lo = mid + 1
        else:
            hi = mid
    return lo

441. Arranging Coins (Easy)

Solution

Standard binary search template with minor change.

We need to move to the next level, even when coins(mid) is less than n. It is also obvious when coins(mid) == n, because we always return lo - 1.

When n == 1, answer is always 1.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

def arrangeCoins(self, n: int) -> int:
    coins = lambda i: i * (i + 1) / 2
    lo, hi = 0, n
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if coins(mid) <= n:
            lo = mid + 1
        else:
            hi = mid
    return lo if coins(lo) == n else lo - 1

287. Find the Duplicate Number (Medium)

Also

Solution

Standard binary search template with minor change.

Since the range is [1, n], the expected number for any index would be index + 1.

Analysis

Time Complexity: O(log****_N_**) assuming array is sorted, else O(sort)**

where:

  • N is the length of the array

Space Complexity: O(1)

def findDuplicate(self, nums: List[int]) -> int:
    nums = sorted(nums)
    expected = lambda i: i + 1
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if expected(mid) == nums[mid]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

Single Element in a Sorted Array (M)

Problem

Suppose we are given a**sorted**array that only consists of**integers**, where every element appears**twice**, except for one element which appears**once**. Find the element that appears only once.

Constraints:

1 <= nums.length <= 10^3

0 <= nums[i] <= 10^3

Example 1:

Input: [1, 1, 2, 3, 3, 4, 4, 8, 8]

Example 2:

Input: [3, 3, 7, 7, 10, 11, 11]

Example 3:

Input: [1, 1, 2, 2, 3]

Example 4:

Input: [1]

Solution

Since the array contains one element that appears only once, and all of the other elements appear twice, it must always have an odd number of elements.

Lets consider the length of the right part of the array right_len = hi - mid, the single element will only be present in right array if the length is odd. If its even, then we should look into left array. This can be done recursively until we find a single element.

When calculating the mid, if the element at both mid and mid + 1 are equal, we can move the mid to mid - 1 because both the elements are present and when both are added to the right array, parity (odd/even) won’t change.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

def singleNonDuplicate(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == nums[mid + 1]:
            mid -= 1
        right_len = hi - mid
        if right_len % 2 == 1:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

Math - Square

69. Sqrt(x) (Easy)

Also

Solution

<= is required so that the lo will always point to the next integer of the square root. 3 for 2, 2.5, 2.9) and the return lo - 1

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is given number

Space Complexity: O(1)

def mySqrt(self, x: int) -> int:
    square = lambda i: i * i
    lo, hi = 0, x
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if square(mid) <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo if square(lo) == x else lo - 1

367. Valid Perfect Square (Easy)

Also

Solution

This is very similar to 69. Sqrt(x) (Easy) but instead of returning the lo - 1, return if square of lo - 1 is equal to given num

<= is required so that the lo will always point to the next integer of the square root. 3 for 2, 2.5, 2.9) and the return lo - 1

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is given number

Space Complexity: O(1)

def isPerfectSquare(self, num: int) -> bool:
    square = lambda i: i * i
    lo, hi = 0, num
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if square(mid) <= num:
            lo = mid + 1
        else:
            hi = mid
    lo = lo if square(lo) == num else lo - 1
    return square(lo) == num

633. Sum of Square Numbers (Medium)

Solution

For any particular \(a\) chosen, the value of \(b\) required to satisfy the equation \(a^2+b^2=c^2\) will be such that \(b^2=c-a^2\). Thus, we need to traverse over the range \((0, \sqrt{c})\) only for considering the various values of \(a\). For every current value of \(a\) chosen, we can determine the corresponding \(b^2\) value and check if it is a perfect square or not. If it happens to be a perfect square, \(c\) is a sum of squares of two integers, otherwise not.

Analysis

Time Complexity: \(\mathcal{O}(\sqrt c \cdot \log c)\)

where

  • \(c\) is the given number

Space Complexity:

def judgeSquareSum(self, c: int) -> bool:
    for a in range(0, int(c**0.5) + 1):
        b = c - a * a
        if self.isPerfectSquare(b):
            return True
    return False

Missing Elements

268. Missing Number (Easy)

Solution

Since n = len(arr) itself can be in the array, hi starts from n and not n - 1.

mid can either be equal to or lesser than arr[mid].There is no way that the mid > nums[mid], hence mid >= nums[mid] is used thoughtfully.

Analysis

Time Complexity: O(log****_N_**) assuming the array is sorted. If not, O(sort)**

where:

  • N is length of the array

Space Complexity: O(1)

def missingNumber(self, nums: List[int]) -> int:
    nums.sort()
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if mid >= nums[mid]:
            lo = mid + 1
        else:
            hi = mid
    return lo

1060. Missing Element in Sorted Array (Medium)

Solution

The domain of the numbers starts from nums[0].

Since the answer can overflow len(nums), one have to start hi with len(nums) and not len(nums) - 1. In other words, the missing number can greater than nums[-1].

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is length of the array

Space Complexity: O(1)

def missingElement(self, nums: List[int], k: int) -> int:
    missing = lambda i: nums[i] - nums[0] - i  # Return the number of missing numbers
    lo, hi = 0, len(nums)
    # find first greatest :pyline:`missing` that is <= k
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if missing(mid) < k:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo - 1] + (k - missing(lo - 1))

1539. Kth Missing Positive Number (Easy)

Solution

Very similar to 1060. Missing Element in Sorted Array (Medium) with a minute difference.

  • The domain of the numbers starts from 1 rather than arr[0]. Hence, missing function has been changed to accommodate this difference.

Since the answer can overflow len(arr), one have to start hi with len(arr) and not len(arr) - 1. In other words, the missing number can greater than nums[-1].

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is length of the array

Space Complexity: O(1)

def findKthPositive(self, arr: List[int], k: int) -> int:
    missing = lambda i: arr[i] - 1 - i  # Return the number of missing numbers
    lo, hi = 0, len(arr)
    # find first greatest :pyline:`missing` that is <= k
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if missing(mid) < k:
            lo = mid + 1
        else:
            hi = mid
    return arr[lo - 1] + (k - missing(lo - 1))

Rotated Sorted Array

Find the pivot (M)

Solution

Duplicate elements are allowed in the array

Pivot = minimum element in the array

Note, don’t use lo for making decision to move.

Example array:

!` <https://t7208592.p.clickup-attachments.com/t7208592/569a1f1e-51c3-4e98-9747-b6f4e84de808/image.png>`_

Analysis

Time Complexity: average case - O(log****_N_**); worst case - O(n)**

where:

  • N is the length of the array

In the worst case, the array would contain identical elements and hi -= 1 would make it in O(n). However, in the average case, its O(logN)

Space Complexity: O(1)

def findPivot(self, nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[hi] < nums[mid]:
            lo = mid + 1
        elif nums[hi] > nums[mid]:
            hi = mid
        else:
            hi -= 1
    return lo

154. Find Minimum in Rotated Sorted Array II (Hard)

Solution

Duplicate elements are allowed in the array

Pivot points to minimum element in the array

Very similar to Find the pivot (M), but we need to return the element at the pivot.

Analysis

Time Complexity: average case - O(log****_N_**); worst case - O(n)**

where:

  • N is the length of the array

In the worst case, the array would contain identical elements and hi -= 1 would make it in O(n). However, in the average case, its O(logN)

Space Complexity: O(1)

def findMin(self, nums: List[int]) -> int:
    pivot = self.findPivot(nums)
    return nums[pivot]

153. Find Minimum in Rotated Sorted Array (Medium)

Solution

A special case of Find the pivot (M), in-turn special case of 154. Find Minimum in Rotated Sorted Array II (Hard) with the only difference that only unique elements exists in the array.

Hence, there is no need to have a else case for nums[mid] == nums[hi], therefore trimming off the last else from the solution of Find the pivot (M)

Note that, the solution which works for Find the pivot (M), works well for this problem.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

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

81. Search in Rotated Sorted Array II (Medium) TODO

33. Search in Rotated Sorted Array (Medium)

Also

Solution

Duplicate elements are allowed in the array

Pivot points to minimum element in the array

Very similar to Find the pivot (M), but once we find the pivot we will have 2 ascending array. Just use 2 binary search for 2 array splits.

Analysis

Time Complexity: average case - O(log****_N_**); worst case - O(n)**

where:

  • N is the length of the array

In the worst case, the array would contain identical elements and hi -= 1 would make it in O(n). However, in the average case, its O(logN)

Space Complexity: O(1)

def search(self, nums: List[int], target: int) -> int:
    pivot = self.findPivot(nums)
    left = self.bisect_left(nums, target, lo=0, hi=pivot)
    if left < len(nums) and nums[left] == target:
        return left
    right = self.bisect_left(nums, target, lo=pivot, hi=len(nums))
    if right < len(nums) and nums[right] == target:
        return right
    return -1

Peaks in an Array

162. Find Peak Element (Medium)

Solution

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

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

852. Peak Index in a Mountain Array (Medium)

Also

Solution

A special case of 162. Find Peak Element (Medium) in which only 1 peak is allowed in the problem array. Solution for the 162. Find Peak Element (Medium) works for this problem too.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

def peakIndexInMountainArray(self, arr: List[int]) -> int:
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < arr[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

1095. Find in Mountain Array (Hard)

Also

Solution

Two subproblems:

Note that, we are changing the interface of the input, by creating a new class called CustomMountainArray so that it can be used as an array for other common methods like bisect_left, bisect_left_rev, peakIndexInMountainArray

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

def findInMountainArray(self, target: int, mountain_arr: "MountainArray") -> int:
    mountain_arr = CustomMountainArray(mountain_arr)
    peakIndex = self.peakIndexInMountainArray(mountain_arr)
    left = self.bisect_left(mountain_arr, target, lo=0, hi=peakIndex)
    if mountain_arr[left] == target:
        return left
    right = self.bisect_left_rev(
        mountain_arr, target, lo=peakIndex, hi=len(mountain_arr) - 1
    )
    if right < len(mountain_arr) and mountain_arr[right] == target:
        return right
    return -1


class CustomMountainArray:
    def __init__(self, ma):
        self.mountain_arr = ma

    def __len__(self):
        return self.mountain_arr.length()

    def __getitem__(self, key):
        return self.mountain_arr.get(key)

H Index

275. H-Index II (Medium)

Solution

We need to find a point where cited(mid) == mid. If its not found by the end, return 0.

Analysis

Time Complexity: O(log****_N_**)**

where:

  • N is the length of the array

Space Complexity: O(1)

def hIndex(self, citations: List[int]) -> int:
    cited = lambda i: len(citations) - i
    lo, hi = 0, len(citations) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if cited(mid) > citations[mid]:
            lo = mid + 1
        else:
            hi = mid
    return cited(lo) if citations[lo] >= cited(lo) else 0

274. H-Index (Medium)

Solution

Very similar to 275. H-Index II (Medium), but the array is not sorted here. Sorting the array and applying same logic should work.

Analysis

Time Complexity: O(nlog****_N_**) to sort**

where:

  • N is the length of the array

Space Complexity: O(1)

def hIndex(self, citations: List[int]) -> int:
    citations = sorted(citations)
    cited = lambda i: len(citations) - i
    lo, hi = 0, len(citations) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if cited(mid) > citations[mid]:
            lo = mid + 1
        else:
            hi = mid
    return cited(lo) if citations[lo] >= cited(lo) else 0