June Leet Code Selection
Leet Code Practice Selection
32. Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
Solution
- I took me a while to solve this question. I actually failed solving, only then looked at the solutions and rewrote the two approach.
- My failed attempt was on counting the paranthesis. A valid substring will
have a 0-sum over left right paranthesis. I jumped into coding and failed.
This is not a necessary condition.
)(
is not valid but has zero sum. - I think the key for solving the problem is to understand the structure in the
solution. A valid substring can not end with
(
. If it ends with)
there should be a matching paranthesis before. - Solution 1: Use a stack to keep track of elements seen. Start from the beginning
Whenever we see
)
look at the top of the stack and if it matches pop it. For example(()
this would end up with single element in stack(
. To determine the size we will use the index of current element from the last elements in the stack. If there is nothing in the stack, this means we match everything before and therefore the length isi+1
. - Solution 2: This solution uses an array
longest[i]
which gives the longest substring seen until element i. Since a substring can only end with)
we only process those indices. There are 2 conditions for a substring to end at index i. (1) longest[i-1]==0 and s[i-1]==’(‘ (2) longest[i-1]!=0 and s[i-longest[i-1]-1]==’(‘. Note that just checkings[i-longest[i-1]-1]=='('
satisfies both conditions as long as the difference is a valid index. If there is a substring ending at i, only thing left is calculating the length and updating the max.
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
stack = []
c_max = 0
for i in range(len(s)):
if s[i] == ')' and stack and s[stack[-1]] == '(':
stack.pop()
start = stack[-1] if stack else -1
c_max = max(c_max, i - start)
else:
stack.append(i)
return c_max
def longestValidParentheses2(self, s):
"""
:type s: str
:rtype: int
"""
longest = [0]*len(s)
c_max = 0
for i in range(1, len(s)):
if s[i] == ')':
if (i-longest[i-1]-1)>=0 and s[i-longest[i-1]-1] == '(':
longest[i] = 2 + longest[i-1]
if (i-longest[i-1]-2)>0:
longest[i] += longest[i-longest[i-1]-2]
c_max = max(c_max, longest[i])
return c_max
496. Next Greater Element I
You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.
The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.
Solution
- We will sweep through the elements of the second array and whenever we encounter an element from first array we add it to the stack.
- During our sweep we will also check whether it greater than any element in the stack.
If so we have our next big element. Note that the elements in stack must be decreasing.
def nextGreaterElement(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ stack = [] set_nums1 = set(nums1) res_dict = {} for el in nums2: while stack and stack[-1]<el: res_dict[stack.pop()] = el if el in set_nums1: stack.append(el) return [res_dict.get(el, -1) for el in nums1]
189. Rotate Array
Given an array, rotate the array to the right by k steps, where k is non-negative.
Solution
- Starting with taking the modulo so that we don’t do extra rotation.
- Let’s do inplace with constant space. For that we will cycle through until we end up in the index we started.
- There might be more than one cycles. So we increment the starting point by one
and repeat until our assign counter ticks the length of the array. Then, we stop
def rotate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: None Do not return anything, modify nums in-place instead. """ k = k % len(nums) if k==0: return nums assign_counter = i = 0 while assign_counter != len(nums): temp = nums[i] prev_j, j = i, (i - k) % len(nums) while j != i: nums[prev_j] = nums[j] assign_counter += 1 prev_j, j = j, (j - k) % len(nums) nums[prev_j] = temp assign_counter += 1 i += 1