Forem: Shailesh Kumar

No. Of Recent Calls | Leetcode October Day 1

Shailesh Kumar — Thu, 01 Oct 2020 12:13:23 +0000

Problem -
"""
You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

RecentCounter() Initializes the counter with zero recent requests.
int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].
It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Example 1:

Input
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
Output
[null, 1, 2, 3, 3
"""

Solution -
Intution- Using queue, remove the stale requests which are older than 3000 seconds

from collections import deque
class RecentCounter:

    def __init__(self):
        self.q = deque()

    def ping(self, t: int) -> int:
        lb = t-3000
        while len(self.q) and self.q[0] < lb:
            self.q.popleft()
        self.q.append(t)
        return len(self.q)

Word Break | Leetcode Day 29

Shailesh Kumar — Wed, 30 Sep 2020 06:39:12 +0000

Problem -

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Example
"""
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

"""

Solution -

One possible optimization is that instead of iterating and checking all substrings, we know what len substrings are present in dictionary and we check for only those lengths.

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s)+1)
        dp[0] = True
        d = set(wordDict)
        for i in range(len(s)):
            for word in wordDict:
                l = len(word)
                if i+1-l >= 0 and s[i+1-l:i+1] in d and dp[i+1-l]:
                    dp[i+1] = True
                    break
        return dp[-1]

Evaluate Division | Leetcode Day 24

Shailesh Kumar — Mon, 28 Sep 2020 07:30:16 +0000

Problem -

You are given equations in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating-point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

Intution - Find the path from source to destination, multiply the edge weights
Solution -

from collections import defaultdict
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        g = defaultdict(list)
        for i in range(len(equations)):
            eq = equations[i]
            val = values[i]
            s, d = eq
            g[s].append((d, val))
            g[d].append((s, 1/val))
        head = (equations[0][0], 1)
        # print(g)
        def dfs(root, path, s, d):
            nonlocal st
            st.add(root[0])
            path = path + [root]
            if s in st and d in st:
                return path
            res = None
            for child in g.get(root[0], []):
                if child[0] not in st:
                    res =  dfs(child, path, s, d)
                    if res is not None:
                        return res
        ans = []
        for s, d in queries:
            if s == d:
                if s in g:
                    ans.append(1)
                else:
                    ans.append(-1)
                continue
            st = set()
            path = dfs((s, 1), [], s, d)
            if path is None:
                st = set()
                path = dfs((d, 1), [], s, d)
            if path is None:
                ans.append(-1)
            else:
                flag = False
                res = 1
                id_p = [el[0] for el in path]
                s_i = id_p.index(s)
                e_i = id_p.index(d)
                if s_i <= e_i:
                    for i in range(s_i + 1, e_i + 1):
                        res*= path[i][1]
                    ans.append(res)
                else:
                    for i in range(s_i, e_i, -1):
                        res *= 1/path[i][1]
                    ans.append(res)
        return ans

LeetCode Day26 | Temo Attacking | Solution Beats 100%

Shailesh Kumar — Sat, 26 Sep 2020 09:16:20 +0000

Teemo Attacking

Solution (Beats 100 %-

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        ans = 0
        last = 0
        for val in timeSeries:
                ans += min(val+duration - last, duration)
                last = val+duration
        return ans

Largest Number | Leetcode Day 25

Shailesh Kumar — Sat, 26 Sep 2020 08:35:20 +0000

Given a list of non negative integers, arrange them such that they form the largest number.

Example - """
Input: [10,2]
Output: "210"
"""

Solution -

import functools
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def sorted_by(a, b):
            if a+b > b+a:
                return 1
            elif a+b < b+a:
                return -1
            else:
                return 0
        cmp = functools.cmp_to_key(sorted_by)
        return "".join(sorted([str(x) for x in nums], key=cmp, reverse=True)).lstrip('0') or '0'

Find the Difference Between Two Strings | LeetCode Day 24

Shailesh Kumar — Fri, 25 Sep 2020 06:37:31 +0000

Problem

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Solution -

from collections import Counter
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        c1 = Counter(s)
        c2 = Counter(t)
        for k2, v2 in c2.items():
            v1 = c1.get(k2, 0)
            if v1 != v2:
                return k2

Leetcode September Day18

Shailesh Kumar — Sat, 19 Sep 2020 05:45:44 +0000

Problem -

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example
"""
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
"""
Solution

Approach - Using deque. Using deque to keep track of maximum price to the right. We then iterate again and update the maximum profit.
TC = O(nlogn)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # we can use stack based approach
        stack = []
        ans = [0] * len(prices)
        for i in range(len(prices)-1, -1, -1):
            if i == len(prices)-1:
                stack.append(prices[i])
                continue
            while True:
                if prices[i] > stack[-1]:
                    stack.pop()
                    if len(stack) == 0:
                        stack.append(prices[i])
                        ans[i] = prices[i]
                        break
                else:
                    stack.append(prices[i])
                    ans[i] = stack[0]
                    break
        res = 0
        for a, m in zip(ans, prices):
            res = max(res, a - m)
        return res

We can still optimize this approach. For each smaller element we are interested in the greater elements to the right. So, while iterating the array, we can arrive at two possibilities -

New element is greater than our current_min, in that case we update our max_profit.
New element is smaller than our current_min, in that case we update our current_min. Solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        current_min = float('inf')
        max_profit = 0
        for price in prices:
            if price < current_min:
                current_min = price
            else:
                max_profit = max(max_profit, price - current_min)
        return max_profit

Edit -
Was trying to have some fun and came up with this one liner

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return reduce(lambda p,c: (max(p[0], c - p[-1]) , min(p[-1], c)) if type(p) == type((1,2,)) else (0, c), [0] + prices)[0] if prices else 0

Leetcode September Day 17

Shailesh Kumar — Thu, 17 Sep 2020 13:16:51 +0000

Problem

On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

"G": go straight 1 unit;
"L": turn 90 degrees to the left;
"R": turn 90 degress to the right.
The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example =
"""
Input: "GGLLGG"
Output: true
Explanation:
The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.
"""

Solution -

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        state_transitions = {
            'jl': '-i',
            '-jl': 'i',
            'il': 'j',
            '-il': '-j',
            'jr': 'i',
            '-jr': '-i',
            'ir': '-j',
            '-ir': 'j'
        }
        curr_dir = 'j'
        start = (0, 0)
        for ins in instructions:
            if ins == 'G':
                if curr_dir == 'j':
                    start = (start[0], start[1] + 1 )
                if curr_dir == '-j':
                    start = (start[0], start[1] - 1 )
                if curr_dir == 'i':
                    start = (start[0] + 1, start[1] )
                if curr_dir == '-i':
                    start = (start[0] - 1, start[1] )
            if ins == 'L':
                curr_dir = state_transitions[curr_dir+'l']
            if ins == 'R':
                curr_dir = state_transitions[curr_dir+'r']
        if start == (0, 0):
            return True
        else:
            if curr_dir != 'j':
                return True
        return False

Odd Shuffling ( binary search variation)

Shailesh Kumar — Thu, 17 Sep 2020 07:40:29 +0000

Problem Statement -

In a sorted array, the odd indices are divided in two parts. Elements on left are swapped with elements on right. We have to search for index of a given number in that array.

Example -
"""
A = [1, 6, 3, 4, 5, 2]
B = 5
Ans = 4
"""

To Find = index of B.
Approach - We need to solve it in logN. So, we need to use binary search. But, it applies only on sorted arrays.
So, we apply binary search on even indices as they are sorted and try to find B or the number closest to B.

case 1: We are able to find B.
We return the index.
case 2: We are not able to find B.
So, we find the number next to our result. This is where B should reside in a sorted array. so, If that's equal to B we return it else, the number we found is the one that got swapped with B.
to_find = A[ans + 1]
So, we try to do binary search over even indices and find to_find.
Again, If A[ans] = to_find we return it, else we check for + 1 index.
Solution

class Solution:
    # @param A : list of integers
    # @param B : integer
    # @return an integer
    def solve(self, A, B):
        lo = 0
        hi = (len(A)-1)//2
        ans = float('-inf')
        ans_idx = None
        # first search over all even indices
        while lo <= hi:
            mid = (lo + hi)//2
            if A[mid * 2] == B:
                return mid * 2
            else:
                if A[mid * 2] > B:
                    hi = mid - 1
                else:
                    ans = max(ans, A[mid * 2])
                    ans_idx = mid * 2
                    lo = mid + 1
        if A[ans_idx + 1] == B:
            return ans_idx + 1
        to_find = A[ans_idx + 1] # this is the number that was swapped
        # in binary search try to find, this smaller or larger number.
        lo = 0
        hi = (len(A)-1)//2
        ans = float('-inf')
        ans_idx = None
        # first search over all even indices
        while lo <= hi:
            mid = (lo + hi)//2
            if A[mid * 2] == to_find:
                return mid * 2
            else:
                if A[mid * 2] > to_find:
                    hi = mid - 1
                else:
                    ans = max(ans, A[mid * 2])
                    ans_idx = mid * 2
                    lo = mid + 1
        # print('ans', ans_idx, to_find, ans)
        if A[ans_idx + 1] == B:
            return ans_idx + 1
        return - 1

Leetcode September Day16

Shailesh Kumar — Wed, 16 Sep 2020 18:06:54 +0000

Problem

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example
"""
Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.
"""

Approach -
The brute force approach would be to consider all pairs and return the pair with maximum xor.

ans = float('-inf')
for i in range(len(arr)):
    for j in range(i, len(arr)):
        ans = max(ans, arr[i]^arr[j])
return ans

Time Complexity of this approach is O(n^2) and space complexity is O(1).

How can we optimize it ?

We know that a^b = 1 if a != b . (assuming a, b to be either 0 or 1).
So, xor of two numbers will be maximum if the they differ in their bits at most places.
For example 11001 will give max xor with 00110 which is 11111.
So, We will first convert all numbers into their binary string representation. Then for each number we will try to find the number with opposite bits (as close as possible) and we update the answer.

Now, to find the number with opposite bits we will be using tries. The time for search in trie is O(len(word)).

Solution

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        bin_list = ["{0:b}".format(el) for el in nums]
        max_len = len(max(bin_list, key = lambda x: len(x)))
        bin_list = ["0"*(max_len - len(el)) + el for el in bin_list]
        ans = float('-inf')
        # create a trie and for each representation try to find the exact opposite as much as possible
        trie = {}
        for word in bin_list:
            parent = trie
            for char in (word):
                if char in parent:
                    parent = parent[char]
                else:
                    parent[char] = {}
                    parent = parent[char]
        # now for each item in binary_list, try to find the opposite
        ans = float('-inf')
        for word in bin_list:
            parent = trie
            curr = ''
            for idx, char in enumerate(word):
                to_find = '1' if char == '0' else '0'
                if to_find in parent:
                    curr += to_find
                    parent = parent[to_find]
                else:
                    curr += char
                    parent = parent[char]
                if idx == len(word) - 1:
                    ans = max(ans, int(word, 2) ^ int(curr, 2) )
        return ans

Time Complexity -
For creating binary list = O(n*log(len_of_digits)) = O(n)
for each word we are search in trie = O(n*log(len_of_digits)) = O(n).
So, approximately the time complexity of this solution is O(n).

Leetcode September Day15

Shailesh Kumar — Tue, 15 Sep 2020 16:27:49 +0000

Problem

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word (last word means the last appearing word if we loop from left to right) in the string.

If the last word does not exist, return 0.

Note: A word is defined as a maximal substring consisting of non-space characters only.

Example -
"""
Input: "Hello World"
Output: 5
"""
Approach - This is a fairly straightforward question. We iterate over the string , find the last word and return it's length.
Solution -

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        return len(s.rstrip().split(" ")[-1]) if s else 0

Here, rstrip() removes the trailing spaces from a string. split(" ") splits the string by " " (spaces) and returns an array.

Leetcode September Day14

Shailesh Kumar — Tue, 15 Sep 2020 07:10:59 +0000

Problem -

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police

Example =
"""
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
"""
Intuition - One approach could be to be greedy i.e. pick the max out of three rob it , move on and again pick the max out of the other 3 possibilities.

However, we can miss some cases here, as we don't know what values lie in future.
Consider following scenario - [2,4,8,40]
If we are greedy we will pick 8. But if we pick 4 we would be able to pick 40 as well and result will be 44.
So, greedy won't work here. We need to enumerate all possibilities/states. So, we will do that. And we will use memoization to reduce the Time Complexity. And because we are using memoization, we term it as a dp solution.
Solution -

class Solution:
    def rob(self, nums: List[int]) -> int:
        cache = {}
        def dp(idx):
            if idx < 0:
                return 0
            else:
                res = cache.get(idx, None)
                if res is not None:
                    return res
                else:
                    res = max(dp(idx-1), dp(idx-2) + nums[idx])
                    cache[idx] = res
                    return res
        return dp(len(nums)-1)