K Closest Points to Origin | Medium

Leetcode

Intuition:

  • Calculate the distance, sort it then return the first K element

Gotchas:

  • square root not necessary

Base cases:

  • None

Solution:

class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        points.sort(key=lambda p:(p[0]**2 + p[1]**2))
        return points[:K]


# Using 
class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        heap = []
        for p in points:
            d = -(p[0]**2 + p[1]**2)
            heapq.heappush(heap, (d,p))
            if len(heap) > K:
                heapq.heappop(heap)
        return [p for d,p in heap]

Complexity Analysis:

O(N …

more ...

Remove Invalid Parentheses | Hard

Leetcode

Intuition:

- Use DFS to recursively either remove the character or just continue.

Gotchas:

- The program expects empty string in the answer if there are no other matches
- non-parenthesis characters is like a no-op character, that moves the iterator without doing anything.
- The answer needs to be in set to avoid duplicates
- left parenthesis(L) has a preferential consideration over right parenthesis(R) since R is an invariant if there is more R than L at any given position.

Base case:

- The resulting answer should have a matching number of parenthesis.
- Iteration ends when the iteration reaches the end of …
more ...

Minimum Remove to Make Valid Parentheses | Medium

Leetcode

Intuition:

  • Calculate the invariant (out of place) parentheses first and then remove them.

Gotchas:

  • Unlike getting all possibilities, this doesn't require recursion / search / stack or queue.
  • Trying to solve by looping in sequence doesn't work. Right parentheses can be removed in sequence, but Left parentheses are efficiently removed in reverse.
  • Character can be set to "" instead of creating a new string

Base cases:

  • None for loops.
  • Splitting the string into a char list makes it easier to "remove" a character

Solution:

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:

        left_rem = 0
        s = [c for c in s ]
        N = len …
more ...

Product of Array Except Self | Medium

Leetcode

Intuition:

  • Create a left list that should be cumulative of [0:i-1] for given i
  • Create a right list that should be cumulative of [i+1:-1] for a given i
  • return list of left[i] * right[~i]

Gotchas:

  • Either the multiplied sum needs to be applied at the proper location AND iteration needs to exclude the last element
  • or there is implied 1 multiplication due to the shift in the iteration

Base cases:

  • Initialize the answer as list of 1
  • Or initialize the left and right accumulation list with implied 1

Solution (Optimized, prealloc):

class Solution(object):
    def …
more ...

Valid Palindrome II

https://leetcode.com/problems/valid-palindrome-ii/

Intuition:

  • Set two iterators from the beginning and the end and make adjustments

Gotchas:

  • the deletion might be needed from the either side of the iteration. So from the point of the mismatch, two verifications are needed
  • slicing the char character may be tricky

Base cases:

  • None

Solution:

class Solution:
    def validPalindrome(self, s: str) -> bool:
        i = 0
        j = len(s) - 1
        used = False
        while i <= j:
            if not s[i] == s[j]:
                return s[i:j] == s[i:j][::-1] or s[i+1:j+1] == s[i+1:j+1][::-1] # indexing
            i …
more ...

Verifying an Alien Dictionary | Easy

Leetcode

Intuition:

  • Store the alien alphabet in a dictionary so that lookup can be in O(1)

Gotchas

  • Not all characters need to be verified, only when the characters are equal
  • The words might not be of the same length

Base case:

  • at least two words to be given

Solution:

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        order = { v:k for k,v in enumerate(order) }
        if len(words) < 2:
            return True
        i = 0
        j = 1
        def compareWords(w1, w2):
            i = 0
            j = 0
            while i < len(w1) and j < len(w2):
                if order[w1[i …
more ...