Home

32. Longest Valid Parentheses Solution - Stack Reference Use stack to keep track of all indexes. When a valid parentheses pair is found, pop the indexes out. Otherwise push. Thus the substring between each index in the stack is valid. Get the longest one. def longestValidParentheses(self, s): """ ...

45. Jump Game II Solution At each step, we can jump at a range [l, r]. l is where we end up with at the previous step. All positions before it was checked already. Keep the right most position r that one can jump within times jump. When r == len(nums) - 1, we have reached our goal. def jump(self, num...

41. First Missing Positive Solution The result should be maximally n, the length of nums. We can use nums to keep track of which number is missing. For any appeared num, set nums[num] to None. Ignore all negative and num > n. The first index of not None is the result. def firstMissingPositive(self...

1582. Special Positions in a Binary Matrix Given a rows x cols matrix mat, where mat[i][j] is either 0 or 1, return the number of special positions in mat. A position (i,j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed). Solution Track the sum of each row and col...

344. Reverse String Solution Reverse from both start and end. def reverseString(self, s): """ :type s: List[str] :rtype: None Do not return anything, modify s in-place instead. """ l = len(s) for i in range(l // 2): lc, rc = s[i], s[l-1-i] tmp = lc s[i] = rc s[l-1-i] = tmp

328. Odd Even Linked List Solution Use two pointer to keep track of odd and even nodes. Note to deal with head.next.next when head.next is None def oddEvenList(self, head): """ :type head: ListNode :rtype: ListNode """ dummy1 = odd = ListNode(0) dummy2 = even = ListNode(0) while head: odd.next = head even.n...

1584. Min Cost to Connect All Points You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi]. The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: xi - xj + yi - yj , where val denotes th...

1583. Count Unhappy Friends You are given a list of preferences for n friends, where n is always even. For each person i, preferences[i] contains a list of friends sorted in the order of preference. In other words, a friend earlier in the list is more preferred than a friend later in the list. Friends in each list are denoted by integers from ...