# LeetCode - Top Interview 150

- https://leetcode.com/studyplan/top-interview-150/
## Array / String
- Merge Sorted Array
- Remove Element
- Remove Duplicates from Sorted Array
- Remove Duplicates from Sorted Array II
- Majority Element
- Rotate Array
- Best Time to Buy and Sell Stock
- Best Time to Buy and Sell Stock II
- Jump Game
- Jump Game II
- H-Index
- Insert Delete GetRandom O(1)
- Product of Array Except Self
- Gas Station
- Candy
- Trapping Rain Water
- Roman to Integer
- Integer to Roman
- Length of Last Word
- Longest Common Prefix
- Reverse Words in a String
- Zigzag Conversion
- Find the Index of the First Occurrence in a String
- Text Justification
## Two Pointers
- Valid Palindrome

def isPalindrome(s):
    l=0
    r=len(s)-1
    while l < r:
        if not s[l].isalnum():
            l += 1
            continue
        if not s[r].isalnum():
            r -= 1
            continue
        if s[l].lower() != s[r].lower():
            return False
        l += 1
        r -= 1
    return True

- Is Subsequence
- Two Sum II - Input Array Is Sorted
- Container With Most Water
- 3Sum
## Sliding Window
- Minimum Size Subarray Sum
- Longest Substring Without Repeating Characters
- Substring with Concatenation of All Words
- Minimum Window Substring
## Matrix
- Valid Sudoku
- Spiral Matrix
- Rotate Image
- Set Matrix Zeroes
- Game of Life

## Bit Manipulation
- Add Binary
- Reverse Bits
- Number of 1 Bits

# TC: O(log n)
# SC: O(1)
def count_set_bits(num):
    result = 0
    while num > 0:
        num = num & (num - 1)
        result += 1

- Single Number

# TC: O(n)
# SC: O(1)
def one_odd_occuring(nums):
    result = 0
    for x in nums:
        result = result ^ x
    return result

- Single Number II
- Bitwise AND of Numbers Range

## Math
- Palindrome Number

# TC: O(log n)
# SC: O(1)
def isPalindrome(self, x):
    rev = 0
    current = x
    while current > 0:
        digit = current % 10
        rev = rev * 10 + digit
        current = current // 10
    if rev == x:
        return True
    return False

- Plus One
- Factorial Trailing Zeroes
- Sqrt(x)
- Pow(x, n)
- Max Points on a Line

## Heap
- Kth Largest Element in an Array

def find_kth_largest(nums, k):
    h = []
    for x in nums:
        if len(h) < k:
            heappush(h, x)
        elif h[0] < x:
                heappush(h, x)
                heappop(h)
    return h[0]

- IPO
- Find K Pairs with Smallest Sums
- Find Median from Data Stream

## Interval
- Summary Ranges

# TC: O(n)
# SC: O(n)

def summary_rannge(nums):
    result = []
    i = 0
    while i < len(nums):
        start = i
        while i + 1 < len(nums) and nums[i] + 1 == nums[i + 1]:
            i += 1
        
        if start == i:
            result.append(str(nums[i]))
        else:
            result.append(f'{nums[start]}->{nums[i]}')
        i += 1
    return result 


print(summary_rannge([0, 1, 2, 4, 5, 7])) # ["0->2", "4->5", "7"]
print(summary_rannge([0, 2, 3, 4, 6, 8, 9])) # ["0", "2->4", "6", "8->9"]

- Merge Intervals

# TC: O(nlogn)
# SC: O(n)

def merge(intervals):
    result = []
    intervals.sort(key=lambda x: x[0])
    for interval in intervals:
        if len(result) == 0 or result[-1][1] < interval[0]:
            result.append(interval)
        else:
            # merge
            result[-1][1] = max(result[-1][1], interval[1])
    return result

print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
print(merge([[1, 4], [4, 5]]))

- Insert Interval

# TC: O(n)
# SC: O(n)

def insert(intervals, new_interval):
    result = []
    i = 0
    n = len(intervals)

    # pre overlap
    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    # overlap
    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)

    # post overlap
    while i < n:
        result.append(intervals[i])
        i += 1
    

    return result

print(insert([[1, 2], [3, 5], [6, 7], [9, 10], [12, 16]], [4, 8]))

- Minimum Number of Arrows to Burst Balloons

# TC: O(n(log n))
def find_min_arrow_shots(points):
    if not points:
        return 0

    # sort by x_end
    points.sort(key = lambda x : x[1])

    arrows = 1
    first_end = points[0][1]
    for x_start, x_end in points:
        # if the current balloon starts after the end of another one,
        # one needs one more arrow
        if first_end < x_start:
            arrows += 1
            first_end = x_end

    return arrows