Leetcode

02 Feb 2022 in Study Blog on Coding Interview

1. Two sum

   • Hashmap
2. Add two numbers
   • Linked List
3. Longest Substring Without Repeating Characters
   • Two pointers
4. Median of Two Sorted Arrays
   • Median
   • Binary Search
5. Longest Palindromic Substring
   • DP
   • Java vs Python
6. Regular Expression Matching
   • Recursion
7. Container With Most Water
   • Two pointers
8. 3 Sum
   • 2 sum
   • Hashmap
   • sort
9. Letter Combinations of a Phone Number
   • Hashmap
   • Recursion
10. Remove Nth Node From End of List
    • Symmetric
    • Two pointers
11. Valid Parentheses
    • Stack
    • Hashmap for pair
12. Generate Parentheses
    • DFS
    • Stack
    • DP
13. Merge k Sorted Lists
    • Priority Queue

        from Queue import PriorityQueue
      

    • Python sorted(list)
14. Reverse Nodes in k-Group
    • Reverse list
    • 6 pointers: dummy, jump, l, r, prev, cur
15. Next Permutation
    • Find Pattern: nums[i-1] < nums[i]
    • Decreasing List
16. Longest Valid Parentheses
    • Find Pattern: If ‘)’ more than ‘(‘, reset
    • Stack
    • Two traverse
17. Search in Rotated Sorted Array
    • Binary Search
    • Mind left <= mid since mid = (left + right)//2
18. Find First and Last Position of Element in Sorted Array
    • Binary Search
    • Find left most: left = mid + 1, right = mid python = while left < right: mid = (left + right) // 2 if nums[mid] < target: left = mid + 1 else: right = mid
    • Find right most: left = mid, right = mid - 1 python = while left < right: mid = (left + right + 1) // 2 if nums[mid] > target: right = mid - 1 else: left = mid
19. Search Insert Position
    • Binary Search
20. Combination Sum
    • Backtracking/DFS

      def dfs(nums, target, path, res):
            if target < 0:
                return
            elif target == 0:
                res.append(path)
            else:
                for i in range(len(nums)):
                    dfs(nums[i:], target - nums[i], path + [nums[i]], res)
      

21. First Missing Positive
    • Find Pattern: [1,2,...,n+1]
    • Hash nums[nums[i]%n] += n
22. Trapping Rain Water
    • DP: store leftMax and rightMax
    • Two pointers
23. Jump Game II
    • Two pointers: left for n steps, right for n+1 steps
24. Permutations
    • DFS
25. Rotate Image
    • List transportation with zip()
    • rotate = flip + trans
26. Group Anagrams
    • permutations have the same characters: sorted() + dict
27. Maximum Subarray
    • Divide and Conquer
    • DP
28. Jump Game
    • two pointers
    • from end to start: where is the last reachable point
29. Merge Intervals
    • Graph
    • sort() + max()
30. Unique Paths
    • DP
    • Math $C_m^n$
31. Minimum Path Sum
    • DP
32. Climbing Stairs
    • DP
33. Edit Distance
    • DP
34. Search a 2D Matrix
    • Binary Search: $m \times n$ sorted array
    • if element not in list, find the left boundary: mid = (left + right)//2, right -= 1
35. Sort Colors
    • count sort
    • *Dutch National Flag Problem
36. Minimum Window Substring
    • Sliding window, two pointers
37. Subsets
    • Backtracking
    • Bitmask
    • DP
38. Word Search
    • Backtracking / DFS

OA

1. Merge Sort: Counting Inversions

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'countInversions' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts INTEGER_ARRAY arr as parameter.
#

def countInversions(arr):
    # Write your code here
    temp_arr = [0]*len(arr)
    return mergeSort(arr, temp_arr, 0, len(arr) - 1)

def mergeSort(arr, temp_arr, left, right):
    inv_cnt = 0
    if left < right:
        mid = (left + right) // 2
        inv_cnt += mergeSort(arr, temp_arr, left, mid)
        inv_cnt += mergeSort(arr, temp_arr, mid + 1, right)
        inv_cnt += merge(arr, temp_arr, left, mid, right)
    return inv_cnt

def merge(arr, temp_arr, left, mid, right):
    i, j, k = left, mid+1, left
    inv_cnt = 0
    while i <= mid and j <= right:
        if arr[i] > arr[j]:
            inv_cnt += mid - i + 1
            temp_arr[k] = arr[j]
            j += 1

        else:
            temp_arr[k] = arr[i]
            i += 1
        k += 1
    
    while i <= mid:
        temp_arr[k] = arr[i]
        i += 1
        k += 1
    while j <= right:
        temp_arr[k] = arr[j]
        j += 1
        k += 1
    
    for x in range(left, right + 1):
        arr[x] = temp_arr[x]
    
    return inv_cnt
    

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        n = int(input().strip())

        arr = list(map(int, input().rstrip().split()))

        result = countInversions(arr)

        fptr.write(str(result) + '\n')

    fptr.close()

1. Stars and Bars: ```python= def stars_and_bars(s, startIndex, endIndex): bars = {}

   cnt = 0 for i in range(len(s)): if s[i] == “|”: bars[i] = cnt cnt += 1 lst = list(bars) startIndex, endIndex = [x-1 for x in startIndex],
   [x-1 for x in endIndex] start_bar, end_bar = [], []

   for i in range(len(startIndex)): start_bar.append(binary_start(lst, startIndex[i])) for i in range(len(endIndex)): end_bar.append(binary_end(lst, endIndex[i]))

   print(bars) print(start_bar, end_bar)

   res = 0 for i in range(len(start_bar)):

    res += max(0, (end_bar[i] - start_bar[i] - 1) - \
               (bars[end_bar[i]] - bars[start_bar[i]] - 1))
   

   return res

def binary_start(nums, target): left, right = 0, len(nums) -1

while left < right:
    mid = (left+right)//2
    if nums[mid] == target:
        return nums[mid]
    elif nums[mid] > target:
        right = mid
    else:
        left = mid + 1
return nums[right]

def binary_end(nums, target): left, right = 0, len(nums) -1

while left < right:
    mid = (left+right+1)//2
    if nums[mid] == target:
        return nums[mid]
    elif nums[mid] > target:
        right = mid - 1
    else:
        left = mid  
return nums[left] ```