Snapshot Array - Python Solution

 Implement a SnapshotArray that supports the following interface:

• SnapshotArray(int length) initializes an array-like data structure with the given length.  Initially, each element equals 0.
• void set(index, val) sets the element at the given index to be equal to val.
• int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
• int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

 

Example 1:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

class SnapshotArray:

    def __init__(self, length: int):
        self.A = [{} for _ in range(length)]
        self.snap_id = 0

    def set(self, index: int, val: int) -> None:
        self.A[index][self.snap_id] = val

    def snap(self) -> int:
        self.snap_id +=1
        return self.snap_id-1

    def get(self, index: int, snap_id: int) -> int:
        snaps = self.A[index]
        if snap_id in snaps:
            return snaps[snap_id]
        else:
            last_val = 0
            for i in range(0,self.snap_id+1):
                if i in snaps:
                    last_val = snaps[i]
                if i >= snap_id:
                    return last_val
            return last_val


# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)

Android Unlock Patterns - Python Solution

 Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.

 

Rules for a valid pattern:

1. Each pattern must connect at least m keys and at most n keys.
2. All the keys must be distinct.
3. If the line connecting two consecutive keys in the pattern passes through any other keys, the other keys must have previously selected in the pattern. No jumps through non selected key is allowed.
4. The order of keys used matters.

 

 

Explanation:

| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |

Invalid move: 4 - 1 - 3 - 6
Line 1 - 3 passes through key 2 which had not been selected in the pattern.

Invalid move: 4 - 1 - 9 - 2
Line 1 - 9 passes through key 5 which had not been selected in the pattern.

Valid move: 2 - 4 - 1 - 3 - 6
Line 1 - 3 is valid because it passes through key 2, which had been selected in the pattern

Valid move: 6 - 5 - 4 - 1 - 9 - 2
Line 1 - 9 is valid because it passes through key 5, which had been selected in the pattern.

 

Example:

Input: m = 1, n = 1
Output: 9

class Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        skip = {}
        skip[(1,3)] = 2
        skip[(1,7)] = 4
        skip[(1,9)] = 5
        skip[(2,8)] = 5
        skip[(3,7)] = 5
        skip[(3,9)] = 6
        skip[(4,6)] = 5
        skip[(7,9)] = 8
        self.ans = 0
        def dfs(visited,k):
            if len(visited) >= m:
                self.ans+=1
            if len(visited) == n:
                return 
            for i in range(1,10):
                if i not in visited:
                    pair = (min(k,i),max(k,i))
                    if pair not in skip or skip[pair] in visited:
                        dfs(visited + [i],i)
        dfs([1],1)
        dfs([2],2)
        self.ans *=4
        dfs([5],5)
        return self.ans

O(n) TC SC O(1)

Find And Replace in String - Python Solution

 To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y.  The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y.  If not, we do nothing.

For example, if we have S = "abcd" and we have some replacement operation i = 2, x = "cd", y = "ffff", then because "cd" starts at position 2 in the original string S, we will replace it with "ffff".

Using another example on S = "abcd", if we have both the replacement operation i = 0, x = "ab", y = "eee", as well as another replacement operation i = 2, x = "ec", y = "ffff", this second operation does nothing because in the original string S[2] = 'c', which doesn't match x[0] = 'e'.

All these operations occur simultaneously.  It's guaranteed that there won't be any overlap in replacement: for example, S = "abc", indexes = [0, 1], sources = ["ab","bc"] is not a valid test case.

Example 1:

Input: S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
Output: "eeebffff"
Explanation: "a" starts at index 0 in S, so it's replaced by "eee".
"cd" starts at index 2 in S, so it's replaced by "ffff".

Example 2:

Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation: "ab" starts at index 0 in S, so it's replaced by "eee". 
"ec" doesn't starts at index 2 in the original S, so we do nothing.

Notes:

1. 0 <= indexes.length = sources.length = targets.length <= 100
2. 0 < indexes[i] < S.length <= 1000
3. All characters in given inputs are lowercase letters.

class Solution:

    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:

        hashmap ={i:(src,tar) for i,src,tar in zip(indexes,sources,targets)}

        result = ""

        i = 0

        while i < len(S):

            if i in hashmap and S[i:].startswith(hashmap[i][0]):

                result +=hashmap[i][1]

                i+=len(hashmap[i][0])

            else:

                result += S[i]

                i+=1

        return result

      

O(N) - > TC and SC

Minimum Window Substring - Python Solution

 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        dict_t = Counter(t)
        required = len(dict_t)
        filtered_s = []
        for i,char in enumerate(s):
            if char in dict_t:
                filtered_s.append((i,char))
        l,r = 0,0
        formed = 0
        window_counts = {}
        ans = float("inf"),None,None
        while r < len(filtered_s):
            character = filtered_s[r][1]
            window_counts[character] = window_counts.get(character,0)+1
            if window_counts[character] == dict_t[character]:
                formed+=1
                
            while l<=r and formed == required:
                character = filtered_s[l][1]
                
                end = filtered_s[r][0]
                start = filtered_s[l][0]
                if end-start+1 < ans[0]:
                    ans = (end-start+1,start,end)
                
                window_counts[character] -=1
                if window_counts[character] < dict_t[character]:
                    formed-=1
                l +=1
            r+=1
        return "" if ans[0] == float('inf') else s[ans[1]:ans[2]+1]

TC: O(∣S∣+∣T∣) SC:O(∣S∣+∣T∣)

Longest Substring Without Repeating Characters - Python Solution

 Given a string s, find the length of the longest substring without repeating characters.

 

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        left,right = 0,0
        max_len = 0
        hashmap = collections.defaultdict()
        while right < n:
            if s[right] in hashmap:
                left = max(hashmap.get(s[right]),left)
            max_len = max(max_len,right-left+1)
            hashmap[s[right]] = right+1
            right = right+1
        return max_len  

TC: O(n) SC: O(n)

Longest Substring with At Most K Distinct Characters - Python Solution

 Given a string, find the length of the longest substring T that contains at most k distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        n = len(s)
        if n <= k:
            return n
        left,right = 0,0
        max_len = k
        hashmap = collections.defaultdict()
        while right < n:
            # inserting the last index of the distinct elements
            if len(hashmap) <= k:
                hashmap[s[right]] = right
                right+=1
            
            # when we have more than k distinct elements
            #we need to move the left pointer 
            if len(hashmap) == k+1:
                del_idx = min(hashmap.values())
                del hashmap[s[del_idx]]
                left = del_idx+1
            max_len = max(max_len,right-left)
        return max_len   

TC: O(n) SC: O(n)

Longest Substring with At Most Two Distinct Characters - Python Solution

 Given a string s , find the length of the longest substring t  that contains at most 2 distinct characters.

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        k = 3
        n = len(s)
        if n < k:
            return n
        left,right = 0,0
        max_len = 2
        hashmap = collections.defaultdict()
        while right < n:
            # inserting the last index of the distinct elements
            if len(hashmap) < k:
                hashmap[s[right]] = right
                right+=1
            
            # when we have more than k-1 or 2 distinct elements
            #we need to move the left pointer 
            if len(hashmap) == k:
                del_idx = min(hashmap.values())
                del hashmap[s[del_idx]]
                left = del_idx+1
            max_len = max(max_len,right-left)
        return max_len   
                

TC: O(n) SC: O(n)

Shortest Path in a Grid with Obstacles Elimination - Python Solution

 Given a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m-1, n-1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

 

Example 1:

Input: 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
Output: 6
Explanation: 
The shortest path without eliminating any obstacle is 10. 
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

 

Example 2:

Input: 
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
Output: -1
Explanation: 
We need to eliminate at least two obstacles to find such a walk.

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int: 
        if len(grid) == 1 and len(grid[0]) == 1:
            return 0

        queue = deque([(0,0,k,0)]) // 
        visited = set([(0,0,k)])

        if k > (len(grid)-1 + len(grid[0])-1):
            return len(grid)-1 + len(grid[0])-1

        while queue:
            row, col, eliminate, steps = queue.popleft()
            for new_row, new_col in [(row-1,col), (row,col+1), (row+1, col), (row, col-1)]:
                if (new_row >= 0 and
                    new_row < len(grid) and
                    new_col >= 0 and
                    new_col < len(grid[0])):
                    if grid[new_row][new_col] == 1 and eliminate > 0 and (new_row, new_col, eliminate-1) not in visited:
                        visited.add((new_row, new_col, eliminate-1))
                        queue.append((new_row, new_col, eliminate-1, steps+1))
                    if grid[new_row][new_col] == 0 and (new_row, new_col, eliminate) not in visited:
                        if new_row == len(grid)-1 and new_col == len(grid[0])-1:
                            return steps+1
                        visited.add((new_row, new_col, eliminate))
                        queue.append((new_row, new_col, eliminate, steps+1))

        return -1
            
        

Implement Trie (Prefix Tree) - Python Solution

 Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

class TrieNode:
    def __init__(self):
        self.word = False
        self.children = {}
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for w in word:
            if w not in node.children:
                node.children[w] = TrieNode()
            node = node.children[w]
        node.word = True
        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for w in word:
            if w not in node.children:
                return False
            node = node.children[w]
        return node.word

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for p in prefix:
            if p not in node.children:
                return False
            node = node.children[p]
        return True
        


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Count of Smaller Numbers After Self Python Leetcode

 You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

 

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

class Solution:
    def countSmaller(self, nums):
        def sort(enum):
            half = len(enum) // 2
            if half:
                left, right = sort(enum[:half]), sort(enum[half:])
                for i in range(len(enum)-1,-1,-1):
                    if not right or left and left[-1][1] > right[-1][1]:
                        smaller[left[-1][0]] += len(right)
                        enum[i] = left.pop()
                    else:
                        enum[i] = right.pop()
            return enum
        smaller = [0] * len(nums)
        sort(list(enumerate(nums)))
        return smaller

TN: O(NlogN) SC: O(N)

Read N Characters Given Read4 II - Call multiple times - Python Solution

 Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.

 

Method read4:

The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf.

The return value is the number of actual characters read.

Note that read4() has its own file pointer, much like FILE *fp in C.

Definition of read4:

    Parameter:  char[] buf4
    Returns:    int

Note: buf4[] is destination not source, the results from read4 will be copied to buf4[]

Below is a high level example of how read4 works:

File file("abcde"); // File is "abcde", initially file pointer (fp) points to 'a'
char[] buf = new char[4]; // Create buffer with enough space to store characters
read4(buf4); // read4 returns 4. Now buf = "abcd", fp points to 'e'
read4(buf4); // read4 returns 1. Now buf = "e", fp points to end of file
read4(buf4); // read4 returns 0. Now buf = "", fp points to end of file

 

Method read:

By using the read4 method, implement the method read that reads n characters from the file and store it in the buffer array buf. Consider that you cannot manipulate the file directly.

The return value is the number of actual characters read.

Definition of read:

    Parameters:	char[] buf, int n
    Returns:	int

Note: buf[] is destination not source, you will need to write the results to buf[]

 

Example 1:

File file("abc");
Solution sol;
// Assume buf is allocated and guaranteed to have enough space for storing all characters from the file.
sol.read(buf, 1); // After calling your read method, buf should contain "a". We read a total of 1 character from the file, so return 1.
sol.read(buf, 2); // Now buf should contain "bc". We read a total of 2 characters from the file, so return 2.
sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.

Example 2:

File file("abc");
Solution sol;
sol.read(buf, 4); // After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3.
sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.

 

Note:

• Consider that you cannot manipulate the file directly, the file is only accesible for read4 but not for read.
• The read function may be called multiple times.
• Please remember to RESET your class variables declared in Solution, as static/class variables are persisted across multiple test cases. Please see here for more details.
• You may assume the destination buffer array, buf, is guaranteed to have enough space for storing n characters.
• It is guaranteed that in a given test case the same buffer buf is called by read.

# The read4 API is already defined for you.

# def read4(buf4: List[str]) -> int:

class Solution(object):

    def __init__(self):

        self.tmp = [None] * 4

        self.tmppoint = 0

        self.tmpcount = 0

    def read(self, buf: List[str], n: int) -> int:

        total = 0

        while total < n:

            if self.tmppoint == 0:

                self.tmpcount = read4(self.tmp)

            if self.tmpcount == 0: break

            while self.tmppoint < self.tmpcount and total < n:

                buf[total] = self.tmp[self.tmppoint]

                total+=1

                self.tmppoint+=1

            

            if self.tmppoint == self.tmpcount: self.tmppoint = 0

            if self.tmpcount < 4: break

        return total

TC:O(n)

SC:O(n) buffer space