sophryu99 / algorithm Goto Github PK

View Code? Open in Web Editor NEW

4.0 2.0 1.0 408 KB

algorithm in python - 4 questions a week

Python 100.00%

algorithm leetcode algorithms python

algorithm's People

Contributors

Stargazers

Watchers

Forkers

wonhyung64

algorithm's Issues

647. Palindromic Substrings

Approach

https://leetcode.com/problems/palindromic-substrings/description/

Expansion from center approach
Given the length of the string is N, the number of possible center points are 2N - 1. Between S[0] and S[1], at S[1], between S[1] and S[2], at S[2], etc.

Iterate over 2N - 1 centers, and have the left and the right pointers to cover both cases where the center point overlaps, or are consecutive points
Left = i // 2, Right = (i+1)//2
Expand the left and right pointers, and increment count for every occurrences of palindrome

class Solution:
    def countSubstrings(self, s):
        cnt = 0
        N = len(s)
        for i in range(2 * N - 1):
            left = i // 2
            right = (i + 1) // 2
            while 0 <= left and right < N and s[left] == s[right]:
                left -= 1
                right += 1
                cnt += 1
        return cnt

N: length of the string

Time Complexity: O(N^2) as worst case there will be an expansion till the end of the string for every letter, aaa
Space Complexity: O(1) no extra space used

380. Insert Delete GetRandom O(1)

Approach

https://leetcode.com/problems/insert-delete-getrandom-o1/description/

The intuition would be to create a set for O(1) operation. However, since there is the function getRandom(), creating a set is not efficient as we would first need to convert to list, which will be an overhead for the whole code. This is because set is actually not random as when using integers, elements are popped from the set in the order they appear in the underlying hashtable.

Use a dict and a list
Dict as {int element: index}, and list to keep track of unique int elements
When remove is called, swap the last element of the list with the to-be-removed element
Swap the index of the two elements in the dictionary's index
Pop from the list, and remove from the dict

import random
class RandomizedSet:
    def __init__(self):
        self.d = {}
        self.l = []

    def insert(self, val: int) -> bool:
        if val not in self.d:
            # Store the index of the int ele
            self.d[val] = len(self.l)
            self.l.append(val)
            return True
        return False
        
    def remove(self, val: int) -> bool:
        if val not in self.d:
            return False
        
        l_ele = self.l[-1]
        r_index = self.d[val]

        # Replace the index
        self.d[l_ele] = r_index
        self.l[r_index] = l_ele
        
        # Remove from list and dict
        self.l[-1] = val
        self.l.pop()
        self.d.pop(val)
        return True

    def getRandom(self) -> int:
        return random.choice(self.l)
        
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

Example

element_to_remove = 7

before:     [4, 7, 9, 3, 5]
after:      [4, 5, 9, 3]

before:     {4:0, 7:1, 9:2, 3:3, 5:4}
after:      {4:0, 9:2, 3:3, 5:1}

n: array size

Time Complexity: O(1) with pop, add and get random operation
Space Complexity: O(n) with dict and list

206. Reverse Linked List

Approach

https://leetcode.com/problems/reverse-linked-list/

Create a copy of the whole ListNode
Rotate the head LL
Set the curr.next as prev which contains the curr state before this iteration
Set prev as the current rotated array

# First Iteration------
Initial head: ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: None}}}
# Create a copy of the original ListNode head 
curr:         ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: None}}}
# Rotate the original head
head reset:   ListNode{val: 2, next: ListNode{val: 3, next: None}}
# Set the curr.next as prev which contains the curr state before this iteration
curr:         ListNode{val: 1, next: None}
# Set prev as the current rotated array
prev:         ListNode{val: 1, next: None}

# Second Iteration------
Initial head: ListNode{val: 2, next: ListNode{val: 3, next: None}}
curr: ListNode{val: 2, next: ListNode{val: 3, next: None}}
head reset: ListNode{val: 3, next: None}
curr: ListNode{val: 2, next: ListNode{val: 1, next: None}}
prev: ListNode{val: 2, next: ListNode{val: 1, next: None}}

# Third Iteration-----
Initial head: ListNode{val: 3, next: None}
curr: ListNode{val: 3, next: None}
head reset: None
curr: ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}
prev: ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        while head:
            # Create a copy of the whole ListNode
            curr = head
            # Rotate the head LL
            head = head.next
            # Set the curr.next as prev which contains the curr state before this iteration
            curr.next = prev
            # Set prev as the current rotated array
            prev = curr
        return prev

n: number of nodes

Time Complexity: O(n) Search through the ListNode
Space Complexity: O(n) Copy of the ListNode

238. Product of Array Except Self

Approach

https://leetcode.com/problems/product-of-array-except-self/

The key is to write an algorithm in O(n) time without using the division operation. If division operation was allowed, the simplest approach would have been getting the product of every elements in the array, and dividing by ith element.

Initialize a base var as 1. This var will contain the incremental product throughout the array scan
Traverse through the list, append the element i to new arr, update the base var as base * arr[i].
Traverse through the list from backwards, update arr[i] = arr[i] * base, then update the base var as base * nums[i]
Return ans array

def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = []
        n = len(nums)
        base = 1
        
        # Scan from the left
        for i in range(n):
            ans.append(base)
            base = base * nums[i]
                
        # Scan from the right
        base = 1
        for i in range(n-1,-1,-1):
            ans[i] = ans[i] * base
            base = base * nums[i]
        return ans

n: length of the array

Time Complexity: O(n) Twice of linear scan through the array
Space Complexity: O(n) answer array

173. Binary Search Tree Iterator

https://leetcode.com/problems/binary-search-tree-iterator/

Approach

In order traversal: Left -> Root -> Right

class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self.pushLeft(root)
        
    def pushLeft(self, root):
        while root:
            self.stack.append(root)
            root = root.left

    # Moves the pointer to the right
    def next(self) -> int:
        node = self.stack.pop()
        # Move the pointer to right
        self.pushLeft(node.right)
        return node.val
        
    def hasNext(self) -> bool:
        return len(self.stack) > 0

Time Complexity:
Space Complexity:

797. All Paths From Source to Target

Approach

https://leetcode.com/problems/all-paths-from-source-to-target/description/

DFS through the DAG
Since the size of the input node is 2 <= n <= 15, the approach does not need to be super efficient

Start from the first node and traverse through the directed edges by calling dfs iteratively
Have the path saved as the parameter to the dfs function
When the traversal reaches the end node (n), append the path to the result and end traversing

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        
        def dfs(path):
            if path[-1] == len(graph) - 1:
                res.append(path)
                return
            
            for v in graph[path[-1]]:
                dfs(path + [v])

        res = []
        dfs([0])
        return res

n: number of edges

Time Complexity: O(n) - O(n^2) depending on the shape of the DAG
Space Complexity: O(n) as result array

https://leetcode.com/problems/all-paths-from-source-to-target/solutions/986429/python-iterative-dfs-with-detailed-time-complexity-visuals/?orderBy=most_votes

ㄹㄹㄹ

146. LRU Cache

https://leetcode.com/problems/lru-cache/description/

The functions get and put must each run in O(1) average time complexity.

Ordered dict approach
Ordered dict: dictionary subclass specially designed to remember the order of items, which is defined by the insertion order of keys.

Initialize an ordered dict to keep track of the (key, val) in the input order
Get method: returns the value associated with a key, moves the called key to the end of the dict
Put method: If the current length of the dict exceeds the capacity, pop the first element from the dictionary. Update the value to the dict.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.size = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache: 
            return -1
        val = self.cache[key]
        self.cache.move_to_end(key) # Ordered dict internal function
        return val

    def put(self, key, val):
        if key in self.cache: 
            del self.cache[key]
        self.cache[key] = val
        if len(self.cache) > self.size:
            self.cache.popitem(last=False)

N: number of input cache

Time Complexity: O(1) with only add, del, move to end operation
Space Complexity: O(N)

1347. Minimum Number of Steps to Make Two Strings Anagram

Approach

https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/description/

Anagram: Words that can be rearranged to form each others

Store the frequency of the letters in both strings in a dictionary
From a dict that has more unique letters, subtract the frequencies
Sum of the remaining dictionary values will be the min number of steps to make two strings anagram

from collections import defaultdict
class Solution:
    def minSteps(self, s: str, t: str) -> int:
        s_dict = defaultdict(int)
        t_dict = defaultdict(int)

        for i in range(len(s)):
            s_dict[s[i]] += 1
            t_dict[t[i]] += 1

        s_count = len(set(s_dict))
        t_count = len(set(t_dict))
        res = 0
        if s_count > t_count:
            for item in s_dict:
                if item in t_dict:
                    s_dict[item] = max(0, s_dict[item] - t_dict[item]) 

            res = sum(s_dict.values())
        else:
            for item in t_dict:
                if item in s_dict:
                    t_dict[item] = max(0, t_dict[item] - s_dict[item]) 

            res = sum(t_dict.values())


        return res

N: length of the strings

Time Complexity: O(n) linear scan through the strings
Space Complexity: O(n) dictionaries

173. Binary Search Tree Iterator

Approach

https://leetcode.com/problems/binary-search-tree-iterator/description/

In-order traversal: Left -> Root -> Right
Initialize an empty stack, push the Left node of the root and continue until it reaches the last node.
hasNext(): checks if there is more to traverse to the right of the pointer.
next(): get the top most node from the stack, move the pointer to the right, and return the value at the pointer.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

# In order traversal: Left -> Root -> Right
class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self.pushLeft(root)
        
    def pushLeft(self, root):
        while root:
            self.stack.append(root)
            root = root.left

    def next(self) -> int:
        node = self.stack.pop()
        # Move the pointer to right
        self.pushLeft(node.right)
        return node.val
        
    def hasNext(self) -> bool:
        return len(self.stack) > 0

# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

n: number of nodes
Time Complexity: O(n)
Memory: O(n)

102. Binary Tree Level Order Traversal

Append the root to the deque
For the current level, iterate through all node and pop the root node

from collections import deque
class Solution:
    def levelOrder(self, root):
        if not root: return []
        queue, res = deque([root]), []
        # Append the root to the deque
        while queue:
            # For the current level, iterate through all node and pop the root node
            cur_level, size = [], len(queue)
            for _ in range(size):
                node = queue.popleft()
                # If there is left chid, append to the queue
                if node.left:
                    queue.append(node.left)
                # If there is right chid, append to the queue
                if node.right:
                    queue.append(node.right)
                # Append the current root node's val to the current level array
                cur_level.append(node.val)
            # Append the current level's val to the res
            res.append(cur_level)
        return res

n: number of node

Time Complexity: O(n) visiting every node once
Space Complexity: O(n) size of the q

1029. Two City Scheduling

Approach

https://leetcode.com/problems/two-city-scheduling/description/

Send everyone to the first city first, and send the half to the other city which has the least difference between the costs

For example costs = [[10,20],[30,200],[400,50],[30,20]] :

Send everyone to the first city which sums to 10 + 30 + 400 + 30 = 470.
Calculate the difference between the cost, 10, 170, -350, -10
Sort the difference and get the cost that has the minimum differences (this means refund)
Evaluate 10 + 30 + 400 + 30 + (-350 -10)

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:
        diff = []
        totalsum = 0
        for i, cost in enumerate(costs):
            diff.append(cost[1] - cost[0])
            totalsum += cost[0]

        # sort by the differences
        diff.sort()
        for i in range(len(costs) // 2):
            totalsum += diff[i]
        return (totalsum)

Time complexity: O(nlog(n)) -> sort()
Space complexity: O(n)

430. Flatten a Multilevel Doubly Linked List

Approach

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/description/

Key idea: binary tree preorder traversal, regarding child as left child, next as right child. Need to get rid of child, and flatten the DLL so that every Node is either prev or next.

Append head to the stack and start to traverse. Pop elements from it and add back its next and child in that order.
This is because we want to visit child first when flattening back the multi-level DLL.
Each time we pop the elements from stack, append it to an extra array
Flatten the extra array by connecting the prev and next node to the current node. Set child to None.

class Solution:
    def flatten(self, head):
        if not head: return head
        stack, order = [head], []

        while stack:
            last = stack.pop()
            order.append(last)
            if last.next:
                stack.append(last.next)
            if last.child:
                stack.append(last.child)
        
        for i in range(len(order) - 1):
            order[i+1].prev = order[i]
            order[i].next = order[i+1]
            order[i].child = None
            
        return order[0]

Example:
Input DLL : [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Order List: [1, 2, 3, 7, 8, 11, 12, 9, 10, 4, 5, 6]

Order List shows the DFS traversal through the Multi-level DLL
Now weave through the order list to connect the prev and the next node to the current node

n: number of nodes

Time Complexity: O(n) - visits every node once
Space Complexity: O(n) - stack

Commit

152. Maximum Product Subarray

Approach

https://leetcode.com/problems/maximum-product-subarray/description/

Main idea is to keep track of the max product and min product as the array contains positive and negative numbers.

We have three choices to make in the array:

If positive, you can get maximum product by multiplying the current element with maximum product calculated so far.
If negative, you can get maximum product by multiplying the current element with minimum product calculated so far.
Current element might be a starting position for maximum product sub array

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_prod, min_prod, ans = nums[0], nums[0], nums[0]
        for i in range(1, len(nums)):
            x = max(nums[i], max_prod*nums[i], min_prod*nums[i])
            y = min(nums[i], max_prod*nums[i], min_prod*nums[i])   
            max_prod, min_prod = x, y
            ans = max(max_prod, ans)
        return ans

n: size of nums array

Time Complexity: O(n) linear scan through the array
Space Complexity: O(1) no extra space used

445. Add Two Numbers II

https://leetcode.com/problems/add-two-numbers-ii/description/

Traverse through the List Nodes, save the values to a stack
Join the stack and get the sum of the two numbers
Loop backwards from the stack and create a new ListNode with the values

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        stck1, stck2 = [], []
        while l1:
            stck1.append(l1.val)
            l1 = l1.next

        while l2:
            stck2.append(l2.val)
            l2 = l2.next

        num1 = int(''.join([str(i) for i in stck1]))
        num2 = int(''.join([str(i) for i in stck2]))

        summ = list(str(num1 + num2))
        
        head = None
        for i in range(len(summ) - 1, -1, -1):
            #create a new node to hold the data
            new_node = ListNode(int(summ[i]))
            #set the next of the new node to the current head
            new_node.next = head
            #set the head of the Linked List to the new head
            head = new_node

        return head

N: length of string1, M: length of string2

Time Complexity: O(N + M) Loop through the string
Space Complexity: O(N + M) with new ListNode

322. Coin Change

Approach

https://leetcode.com/problems/coin-change/description/

Initialize a dp array with size of amount. dp[i]: fewest number of coins that sums to i
For every i (the amount to be summed up to), iterate through the coin array and check
f the coin is less than or equal to i, get the dp[i - coin] value, and compare it with the current dp[i] val. Reset dp[i] with smaller value -> dp[i] = min(dp[i], dp[i - coin] + 1)
If the last element of the dp array has not been reached, return -1

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # BFS approach
        # dp array with the size of amount
        # dp[i] is the fewest number of coins need to sum up to i
        dp = [0] + [float('inf')] * amount
        for i in range(1, amount + 1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i - coin] + 1)

        if dp[-1] == float('inf'):
            return -1
        return dp[-1]

N: amount, M: number of coins

Time Complexity: O(N * M) as for every amount, every coins are tried out
Space Complexity: O(N) dp array of size N

347. Top K Frequent Elements

import heapq
from collections import defaultdict
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        d = defaultdict(int)
        for num in nums:
            d[num] += 1

        heap = []
        for key in d:
            # To convert to maxheap
            heapq.heappush(heap, (-d[key], key))

        res = []
        # Get the k top most elements from the heapq
        for _ in range(k):
            p = heapq.heappop(heap)
            res.append(p[1])
        return res

Time Complexity: O(n) max heap
Space Complexity: O(n)

1656. Design an Ordered Stream

Approach

https://leetcode.com/problems/design-an-ordered-stream/description/

We need to store n incoming value (idKey, value) at the given index. And with every incoming index, we have to check

If the current index is less than the incoming index, then we have to return an empty list
Else, we have to return a sliced list from the incoming index to the first index where there is no insertion yet.

Approach

Initialize a list of size n with None
Maintain the current index with self.ptr
For every insert call, with idKey, value:

Assign the list[idKey-1] to the value # Since array is 0-index reduce 1
Check if the current index is less than incoming index(idKey-1) and return []
Else return sliced list from incoming index(idKey-1) till we do not encounter None.

class OrderedStream:

   def __init__(self, n):
        self.stream = [None]*n
        self.ptr = 0

    def insert(self, idKey, value):
        idKey -= 1
        self.stream[idKey] = value
        if self.ptr < idKey:
            return []
        else:
            while self.ptr < len(self.stream) and self.stream[self.ptr] is not None:
                self.ptr += 1
            return self.stream[idKey:self.ptr]
# Your OrderedStream object will be instantiated and called as such:
# obj = OrderedStream(n)
# param_1 = obj.insert(idKey,value)

Time Complexity: O(1) insertion and slicing of array
Space Complexity: O(n) for the stream array

198. House Robber

https://leetcode.com/problems/house-robber/

Memoization
m[k] = money at the kth house
p[k] = profit at kth house
p[0] = 0, p[1] = m[1]
p[k] = max(p[k-2] + m[k], p[k-3] + m[k])

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        elif len(nums) == 2:
            return max(nums)

        # Create a copy of the original nums array
        p = [0] * (len(nums) + 1)
        p[0] = 0
        p[1] = nums[0]
        p[2] = nums[1]
        for i in range(3, len(p)):
            p[i] = max(p[i - 3]+ nums[i - 1], p[i - 2] + nums[i - 1])

        return max(p)

n: array size

Time complexity: O(n)
Memory complexity: O(n)

1209. Remove All Adjacent Duplicates in String II

Approach

https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/

Initialize a stack with dummy ['', 0] pair. The pair indicates [letter, count]
Iterate through the string and compare with the topmost element from the stack. If there is a match, increment the count.
If the count reaches k, pop from the stack
Continue through the string

class Solution:
    def removeDuplicates(self, s, k):
        stck = [['', 0]]
        for l in s:
            if stck[-1][0] == l:
                stck[-1][1] += 1
                if stck[-1][1] == k:
                    stck.pop()
            else:
                stck.append([l, 1])

        return (''.join([i * j for i, j in stck]))

n: length of string s

Time Complexity: O(n) -> Linear scan through the string
Space Complexity: O(n) -> Stack

33. Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

Binary search after determining if the array is left-rotated or right-rotated
mid = (left + right ) // 2
Left-rotated -> arr[mid] > arr[left]:
3-1. if nums[left] <= target < nums[mid] reset right index right = mid - 1
3-2. Else, left = mid + 1
Right-rotated -> arr[mid] < arr[left]
4-1. If nums[mid] < target and target <= nums[right], reset left index left = mid + 1
4-2. Else, right = mid - 1

"""
Binary Search
nums = [3,4,5,6,0,1,2], target = 3

"""

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid
            # If the current number is larger than the target, move the window 
            """
            Determine if the array is left rotated or right rotated

            Original
            1 2 3 4 5
                mid
            
            
            Left-rotated -> arr[mid] > arr[left]
            2 3 4 5 1
                mid

            Right-rotated -> arr[mid] < arr[left]
            5 1 2 3 4
                mid

            """
            # The array is left rotated
            if nums[mid] >= nums[left]:
                # If the target number is in between the left side of the array, reset right index to continue search on the left side
                if nums[left] <= target and target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1 
            # The array is right rotated
            else:
                # If the target number is in between the right side of the array, reset left index to continue search on the right side
                if nums[mid] < target and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        # If not in the array
        return -1

n: length of the array

Time Complexity: O(log(n)) binary search
Space Complexity: O(1) no extra space used

935. Knight Dialer

https://leetcode.com/problems/knight-dialer/description/

A knight could only move in either 2 horizontal + 1 vertical or 2 vertical + 1 horizontal.
Graph traversal, DP problem with N stops

From a dial pad, store all the possible paths from a number in a dict data structure.
For every iteration of jump (i in range(n)), create a next array of [0] * 10 where next[i] = count of dial pad that can be reached from dial pad i

First iteration

0 [2, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1 [2, 2, 0, 0, 0, 0, 0, 0, 0, 0]
2 [2, 2, 2, 0, 0, 0, 0, 0, 0, 0]
3 [2, 2, 2, 2, 0, 0, 0, 0, 0, 0]
4 [2, 2, 2, 2, 3, 0, 0, 0, 0, 0]
5 [2, 2, 2, 2, 3, 0, 0, 0, 0, 0]
6 [2, 2, 2, 2, 3, 0, 3, 0, 0, 0]
7 [2, 2, 2, 2, 3, 0, 3, 2, 0, 0]
8 [2, 2, 2, 2, 3, 0, 3, 2, 2, 0]
9 [2, 2, 2, 2, 3, 0, 3, 2, 2, 2]

Update the dp array, and continue with the next iteration

class Solution:
    def knightDialer(self, n: int) -> int:
        dct = {
            0:(4,6),
            1:(6,8),
            2:(7,9),
            3:(4,8),
            4:(0,3,9),
            5:(),
            6:(0,1,7),
            7:(2,6),
            8:(1,3),
            9:(2,4)
        }

        num_keys = 10
        dp = [1] * num_keys # dp[i] = number of times the knight can reach dial pad i
        
        for _ in range(n - 1):
            nxt = [0] * num_keys
            for i in dct:
                for j in dct[i]:
                    nxt[i] += dp[j]
                
            dp = nxt

        return sum(dp) % (10**9 + 7)

N: input size N

Time Complexity: O(N * number of dials in dial pad(10) * max size of dict[i] (3) ) -> O(N)
Space Complexity: O(1) with dp array of size 10

Rr

424. Longest Repeating Character Replacement

Approach

https://leetcode.com/problems/longest-repeating-character-replacement/description/

Use a dictionary to store the frequency of the character
The key point is that we only care about the MAXIMUM of the seen values.
Get the length of the current substring r - l + 1, then subtract the MAXIMUM frequency. See if this is <= K for validity.

Time Complexity:
Space Complexity:

https://leetcode.com/problems/longest-repeating-character-replacement/solutions/765776/python-two-pointers-process-for-coding-interviews/

1472. Design Browser History

Approach

https://leetcode.com/problems/design-browser-history/description/

Rather unclear description for the visit() function.

When visit() is called, get rid of the array[curr_pointer:] as the function clears the forward history, append new url
When back() is called, reset the pointer within the boundary. Same with forward()

lass BrowserHistory:

    def __init__(self, homepage: str):
        self.history = [homepage]
        self.pointer = 0

    def visit(self, url: str) -> None:
        self.pointer += 1
        self.history =  self.history[:self.pointer]
        self.history.append(url)

    def back(self, steps: int) -> str:
        self.pointer = max(self.pointer - steps, 0)
        return self.history[self.pointer]
        
    def forward(self, steps: int) -> str:
        self.pointer = min(self.pointer + steps, len(self.history) - 1)
        return self.history[self.pointer]

# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)

N: number of urls

Time Complexity: O(1) with just simple append, return from a stack
Space Complexity: O(n) stack size

394. Decode String

Approach

https://leetcode.com/problems/decode-string/

When we hit an open bracket, we know we have parsed k for the contents of the bracket, so push (current_string, k) to the stack, so we can pop them on closing bracket to duplicate the enclosed string k times.

Iterate through the string and use stack to store (string element, k)
When '[', append to the stack with the current k val and string val, reset the string val
When ']', pop from the stack and append to the result with k occurrences of the string
When int, save it to the k var. For multi-digit k values, k = k * 10 + int(char)

class Solution:
    def decodeString(self, s: str) -> str:
        stck = []
        curr_string = ""
        k = 0

        for char in s:
            if char.isdigit():
                k = k * 10 + int(char)
            
            elif char == '[':
                stck.append((curr_string, k))
                curr_string = ""
                k = 0

            elif char == ']':
                last_string, last_k = stck.pop(-1)
                curr_string = last_string + last_k * curr_string

            else:
                curr_string += char

        return curr_string

N: length of the string

Time Complexity: O(N) linear scan through the string
Space Complexity: O(N) size of stack

https://leetcode.com/problems/decode-string/solutions/87662/python-solution-using-stack/?orderBy=most_votes

5. Longest Palindromic Substring

Approach

https://leetcode.com/problems/longest-palindromic-substring/

For every element in the string, check if the left and the right element of the current element is the same
Check until the left and the right pointer reaches the end of the string
Edge cases where the length of the string is either even or odd: treat it differently by having the start element different

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        for i in range(len(s)):
            # Get the longer string from the search
            res = max(self.helper(i, i, s), self.helper(i, i + 1, s), res, key = len)
        
        return res

    def helper(self, l, r, s):
        while 0 <= l and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1

        return s[l + 1: r]

n: length of the string
Time Complexity: O(n^2) -> Worst case search through every element of the string
Memory: O(1)

200. Number of Islands

https://leetcode.com/problems/number-of-islands/description/

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

BFS Approach

Initialize a deque to use as a queue. For every grid[i][j], initiate bfs if it is 1.
Mark the visited grid[i][j] by flipping the '1' value to 0.
When every possible path starting from land is searched, increment the number of island count

from collections import deque
class Solution:
    def numIslands(self, grid):
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    grid[i][j] = 0 # Mark as visited
                    self.bfs(grid, i, j) # turn the adjancent '1' to '0'
                    count += 1
        return count
    
    def bfs(self,grid, i, j):
        queue = deque([])
        queue.append((i,j))
        while queue:
            qr, qc = queue.popleft()
            directions = [[1,0],[-1,0],[0,1],[0,-1]]
            for dr, dc in directions:
                nr, nc = qr + dr, qc + dc
                if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == '1':
                    queue.append((nr,nc))
                    grid[nr][nc] = 0 # Mark as visited

N: number of elements, M: length of each elements

Time Complexity: O(N*M) Visiting every elements in the grid at most once
Space Complexity: O(N*M) Queue size

1396. Design Underground System

Approach

Use dictionaries for efficient lookup, insertion, and pop
d1 = {customerId: (stationName, time)}, keep track of the customerId as the key, and the checked-in station name and time
d2 = {(startstation, endstation): total time spent between}, keep track of the total time spent between two stations. This is calculated when a customer checks out.
d3 = {(startstation, endstation): number of trips}, keep track of the frequency of the trips between two stations. This is calculated when a customer checks out
Average time calculated from taking the values from d2 and d3

from collections import defaultdict
class UndergroundSystem:

    def __init__(self):
        # {customerId: (stationName, time)}
        self.customer = {}

         # {(startstation, endstation): total time spent between}
        self.pairs = defaultdict(int)

        # {(startstation, endstation): number of trips}
        self.freqs = defaultdict(int)

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.customer[id] = (stationName, t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        # Get the stationName and the time associated with the customerId
        startstation, startTime = self.customer.pop(id)
        self.freqs[(startstation, stationName)] += 1
        self.pairs[(startstation, stationName)] += t - startTime
        
    def getAverageTime(self, startStation: str, endStation: str) -> float:
        return self.pairs[(startStation, endStation)] / self.freqs[(startStation, endStation)]

# Your UndergroundSystem object will be instantiated and called as such:
# obj = UndergroundSystem()
# obj.checkIn(id,stationName,t)
# obj.checkOut(id,stationName,t)
# param_3 = obj.getAverageTime(startStation,endStation)

n: number of inputs

Time Complexity: O(1) simple calculation, insertion and removal
Space Complexity: O(n), dictionaries

79. Word Search

https://leetcode.com/problems/word-search/description/

Iterate through the grid and try dfs if there is a match with the first letter
Dfs function takes (i, j, grid, word) as input param. For every iteration, check if grid[i][j] == word[0] and if i, j is within the grid range. Mark grid[i][j] = '#' and unmark when the dfs is done.
Return true if the input string's length is 0.

from collections import Counter
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
	# Count number of letters in board and store it in a dictionary
        boardDic = defaultdict(int)
        for i in range(len(board)):
            for j in range(len(board[0])):
                boardDic[board[i][j]] += 1

        # Count number of letters in word
        # Check if board has all the letters in the word and they are atleast same count from word
        wordDic = Counter(word)
        for c in wordDic:
            if c not in boardDic or boardDic[c] < wordDic[c]:
                return False

        # Traverse through board and if word[0] == board[i][j], call the DFS function
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    if self.dfs(i, j, 0, board, word):
                        return True

        return False

    def dfs(self, i, j, k, board, word):
        # Recursion will return False if (i,j) is out of bounds or board[i][j] != word[k] which is current letter we need
        if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or \
        k >= len(word) or word[k] != board[i][j]:
            return False

        # If this statement is true then it means we have reach the last letter in the word so we can return True
        if k == len(word) - 1:
            return True

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        for x, y in directions:
            # Since we can't use the same letter twice, I'm changing current board[i][j] to -1 before traversing further
            tmp = board[i][j]
            board[i][j] = -1

            # If dfs returns True then return True so there will be no further dfs
            if self.dfs(i + x, j + y, k + 1, board, word): 
                return True

            board[i][j] = tmp

N: number of items in the array, M: length of every items, L: length of the word

Time Complexity: O(N *M)
Space Complexity: O(L) counter dict

56. Merge Intervals

https://leetcode.com/problems/merge-intervals/

Sort the given array by the first element in ascending order
Use a stack to add the elements, pop from the top when comparing
If there is an overlap, say prev[-1] >= curr[0], create a new interval with [min(prev[0], curr[0], max(prev[1], curr[1])] to cover the maximum range. Replace the top most interval with the new interval
Else, append the interval to the array

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # Sort by the first element asc 
        intervals.sort(key = lambda pairs: pairs[0])
        stck = [intervals[0]]

        for i in range(1, len(intervals)):
            prev = stck[-1]
            if prev[1] >= intervals[i][0]:
                new_interval = [min(prev[0], intervals[i][0]), max(prev[1], intervals[i][1])]
                stck[-1] = new_interval
            else:
                stck.append(intervals[i])

        return stck

N: array size

Time Complexity: O(N) linear scan of the array
Space Complexity: O(N) stack size

155. Min Stack

https://leetcode.com/problems/min-stack/description/

The insight is to keep track of the minimum value so far and push it, along with the number we are pushing, onto the stack.

Push a tuple (number we are pushing, the minimum value so far) to the stack
pop and get from a stack has a constant time complexity

class MinStack:

    def __init__(self):
        self.q = []
        
    def push(self, val: int) -> None:
        if self.q:
            minval = self.q[-1][1]
            if val < minval:
                self.q.append((val, val))
            else:
                self.q.append((val, minval))
        else:
            self.q.append((val, val))

    def pop(self) -> None:
        # O(1)
        self.q.pop()

    def top(self) -> int:
        # O(1)
        return self.q[-1][0]
        
    def getMin(self) -> int:
        # O(1)
        if len(self.q) == 0:
            return None
        return self.q[-1][1]
        


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

n: number of values

Time Complexity: O(1)
Space Complexity: O(n) stack

sophryu99 / algorithm Goto Github PK

algorithm's People

Contributors

Stargazers

Watchers

Forkers

algorithm's Issues

Approach

Approach

Approach

Approach

Approach

Approach

146. LRU Cache

Approach

Approach

102. Binary Tree Level Order Traversal

Approach

Approach

Approach

445. Add Two Numbers II

Approach

347. Top K Frequent Elements

Approach

198. House Robber

Approach

33. Search in Rotated Sorted Array

935. Knight Dialer

Approach

Approach

Approach

Approach

200. Number of Islands

Approach

79. Word Search

56. Merge Intervals

155. Min Stack

Recommend Projects

Recommend Topics

Recommend Org