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 is i+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 checking s[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