Scribbling

276. Paint Fence https://leetcode.com/problems/paint-fence/ Paint Fence - LeetCode Can you solve this real interview question? Paint Fence - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com let dp[i] be # of all ways painting i-th fence: then, dp[i] = num_same(i) + num_diff(i) holds. (where ..

How does one can find the number of pairs in an array that satisfies the below condition? : lower

A dynamic programming approach: Let dp[i, j] be the total number of cases of target[i] corresponding to jth position dp[i, j] = dp[i][j-1] + dp[i-1][j-1] * counter[j, target[i]] 1) Bottom-up import string from functools import lru_cache class Solution: def numWays(self, words: List[str], target: str) -> int: N = len(words[0]) freqs = [{c: 0 for c in string.ascii_lowercase} for _ in range(N)] for..

Greedy solution with heap & deque - append character with 'max frequency' currently - put the appended character to a deque for cool-down from collections import Counter, deque import heapq class Solution: def rearrangeString(self, s: str, k: int) -> str: if k = k: freq, char = q.popleft() if freq >= 1: heapq.heappush(h, (-freq, char)) return ''.join(ret) if len(ret) == len(s) else ""

Fenwick Tree (or Binary Indexed Tree) is very efficient in dealing with range queries, especially when elements get updated occasionally. For how it works, refer to the below video. He elaborates on the principle of the tree in a very clean way. https://www.youtube.com/watch?v=CWDQJGaN1gY&t=160s&ab_channel=TusharRoy-CodingMadeSimple Below is the python implementation of it. class Fenwick: """ Py..

First thing first: To implement an expression tree with "Postfix", we can easily do so with a stack. For the evaluation part: "ABC" might be a bit unfamiliar, but all you need to know about it here is that you cannot initiate an instance with the ABC class (in this case Node class). In addition, an abstract method must be implemented in the child class. import abc from abc import ABC, abstractme..

Video I recommend: https://www.youtube.com/watch?v=SToUyjAsaFk In this post, I will cover "Recursive Descent Parsing". Details about it are well elaborated in the above video. This post is to summarize core concepts and implement the algorithm with an actual code. Goal: Implement a parser that parse an arithmetic experssion. - ( 3 + 5) * -2 Elements: Numbers Infix Operators (+, -, *, /) Prefix O..

Rabin-Karp Algorithm is an efficient algorithm to search a string pattern in a given sentence. The core of the idea is to use hash function to compare strings. Time complexity is O(n), where n is length of the string. However, this is true only when there is no hash collision. Time complexity is O(n * m) if hash function is poorly selected (producing many hash collisions), where m is length of t..

Python does not provide standard library for ordered set or ordered dictionary. However, there's an Apache2 licensed sorted collections library "SortedContainer". You can install the library with the following cmd. pip install sortedcontainers https://www.geeksforgeeks.org/python-sorted-containers-an-introduction/#:~:text=Sorted%20set%20is%20a%20sorted,must%20be%20hashable%20and%20comparable. Py..

I found this problem is pretty similar to 'Russian Doll' prob (https://leetcode.com/problems/russian-doll-envelopes/). Thought process for this problem is: 0> Sort the properties. 1> Let's just assume that attack strictly increases (e.g. 3, 4, 5, ...): then what we should do is to count how many defense values have larger values on their right side. And that's exactly what monotonicly desc stack..