DEV Community: Riyaz

Find minimum in rotated sorted array in Python(code and explanation)

Riyaz — Mon, 21 Feb 2022 10:42:02 +0000

Problem statement
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Intuition
From the question we can easily understand that it is a Binary Search question(Hints - Sorted and expectedTime Complexity-logn).
But we cannot directly apply it.

Implementation
So if the array is rotated then we can say that now the entire array is divided into two different sorted arrays.
for eg.

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

from index 0 to 2 the array is sorted and from index 3 to 3 the array is sorted.
But from index 2 to 3 the array is not sorted.
Also we can say that if any number from array is greater than its first element than it is sorted.Then we will look for our number in right part of array i.e

l = mid + 1

And if any number is less than its first element than it is not sorted from first index to mid.Then we will look for our number in left part of array i.e

h = mid - 1

Also in the array the smallest number will be the number that is smaller than both its previous and next element
Hence we will check

 if nums[mid] < nums[mid-1]:
         return nums[mid]
 if nums[mid+1] < nums[mid]:
         return nums[mid+1]

Code

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

        l, h = 0, len(nums)-1

        if nums[h] > nums[0]:
            return nums[0]
        while l <= h:
            mid = (l+h)//2

            if nums[mid] < nums[mid-1]:
                return nums[mid]
            if nums[mid+1] < nums[mid]:
                return nums[mid+1]

            if nums[mid] > nums[0]:
                l = mid + 1
            else:
                h = mid - 1

Time Complexity
O(logn) as we are using binary search itself with some changes.

Space Complexity
O(1) No extra space required similar to binary search.

Path Sum(code and Explanation)

Riyaz — Wed, 16 Feb 2022 14:31:37 +0000

Problem Statement
Q.)Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum.
Binary tree
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Intuition
Lets say you know this question requires you to use DFS but how are you going to store the individual values of all the node and sum them to find if they are equal to targetSum.
For a complete beginner it may not come handy unless you have practiced a lot of such questions.
Now in the iterative version of DFS you know that you have to use stack to remember visited nodes and traverse further.So you are aware that stack is used to store the nodes.So instead of storing only the nodes in the stack you can also store a tuple inside the stack along with the node’s sum of all the previous node value.Something like this
stack
This little trick is hard to come up with your own,but once you know it you can solve many questions regarding the DFS of Binary Tree i.e now you know that you can use the stack itself to store more data about the binary tree.
SOLUTION:

def pathSum(root):
    if not root: return None
    stack = [(root,root.val,[root.val])]
    ans = []
    while stack:
        node,val,li = stack.pop()
        if not node.left and not node.right and val == targetSum:
            ans.append(li)
        if node.right:
            stack.append((node.right,val+node.right.val,li+[node.right.val]))
        if node.left:
            stack.append((node.left,val+node.left.val,li+[node.left.val]))

    return ans

This trick of storing using tuples in stack will help you solve a lot more questions

Remove Stones to minimize the Total(code and Explanation)

Riyaz — Mon, 14 Feb 2022 14:32:09 +0000

PROBLEM STATEMENT
You are given a 0-indexed integer array piles, where piles[i] represents the number of stones in the ith pile, and an integer k. You should apply the following operation exactly k times:

Choose any piles[i] and remove floor(piles[i] / 2) stones from it.
Notice that you can apply the operation on the same pile more than once.

Return the minimum possible total number of stones remaining after applying the k operations.

floor(x) is the greatest integer that is smaller than or equal to x (i.e., rounds x down).
'''
'''
Example 1:

Input: piles = [5,4,9], k = 2
Output: 12
Explanation: Steps of a possible scenario are:

Apply the operation on pile 2. The resulting piles are [5,4,5].
Apply the operation on pile 0. The resulting piles are [3,4,5]. The total number of stones in [3,4,5] is 12. Example 2:

Input: piles = [4,3,6,7], k = 3
Output: 12
Explanation: Steps of a possible scenario are:

Apply the operation on pile 2. The resulting piles are [4,3,3,7].
Apply the operation on pile 3. The resulting piles are [4,3,3,4].
Apply the operation on pile 0. The resulting piles are [2,3,3,4]. The total number of stones in [2,3,3,4] is 12.

EXPLANATION
Everytime you want the maximum value from the pile to be divided.So we will use a maxheap to store the elements in
greatest to least order and after dividing we push the resultant value again inside the heap
CODE

from heapq import *
class Solution:
    def minStoneSum(self, piles: List[int], k: int) -> int:
        maxHeap = []
        for i in range(len(piles)):
            heappush(maxHeap, -piles[i])

        i = k
        while i > 0:
            temp = heappop(maxHeap)
            x = floor(temp/2)
            heappush(maxHeap,x)
            i -= 1
        return -sum(maxHeap)

Time Complexity
O(KlogN)
Space Complexity
O(N) for storing N elements in heap

'K' Closest Numbers(code and explanation)

Riyaz — Sun, 13 Feb 2022 16:09:07 +0000

Problem Statement
Given a number array and two integers ‘K’ and ‘X’, find ‘K’ closest numbers to ‘X’ in the array.
Return the numbers in the sorted order. ‘X’ is not necessarily present in the array.
Example 1:
Input: [5, 6, 7, 8, 9], K = 3, X = 7
Output: [6, 7, 8]
Example 2:
Input: [2, 4, 5, 6, 9], K = 3, X = 6
Output: [4, 5, 6]
SOLUTION
For finding the closest numbers to X we can simple calculate the absolute difference between X and
all the values from the array.Now we store these values in a pair using tuple (abs diff, value) with the abs difference
along with the value itself
So, for example, [5, 6, 7, 8, 9], K = 3, X = 7
the tuple values would be (2,5), (1,6), (0,7), (1,8), (2,9)
So the value the first value in the tuple, the closest the element is from X
Now we want the top k(3) values from this tuple that are closest to X(7)
Now we can utilize the heap data structure to do so
We can use min heap which will store the tuples in smallest to greatest values
So the heap will look like

            (0,7)
           /     \
         (1,6)   (1,8)
        /    \
      (2,5)  (2,9)

Now we can easily remove the top K elements from this heap which will give the closest numbers
Look at the below code for more clarity
CODE

from heapq import *
def findClosestElements(A,K,X):
    answer = []

    minHeap1 = []
    for num in A:
        heappush(minHeap1, (abs(num-X),num)) #Creates a min heap with tuple values as discussed

    minHeap2 = [] #Remove the top K elements from minHeap1 and store in minHeap2 as we have to maintain order
    n = K
    while n > 0:
        a = heappop(minHeap1)
        heappush(minHeap2, a[1]) #Append top K elements values from the minHeap1 and store the second value 
        n -= 1                   # from the tuple i.e (0,7) --> 7 as '7' is the actual element

    while minHeap2:
        b = heappop(minHeap2) #Remove all the elements from the minHeap2 one by one and store them in answer 
        answer.append(b)

    return answer

Time Complexity
The first step of creating minHeap1 will take O(N)
Creating minHeap2 will take O(KlogK)
So overall time complexity is O(KLogK)
Space Complexity
O(N) for storing N elements in heap

Connect Ropes(code and explanation)

Riyaz — Sun, 13 Feb 2022 16:04:28 +0000

Yet another question on a mixture on Greedy approach utilizing heap data structure
Problem Statement
Given ‘N’ ropes with different lengths, we need to connect these ropes into one big rope with minimum cost.
The cost of connecting two ropes is equal to the sum of their lengths.
Example 1:
Input: [1, 3, 11, 5]
Output: 33
Explanation: First connect 1+3(=4), then 4+5(=9), and then 9+11(=20). So the total cost is 33 (4+9+20)
Example 2:
Input: [3, 4, 5, 6]
Output: 36
Explanation: First connect 3+4(=7), then 5+6(=11), 7+11(=18). Total cost is 36 (7+11+18)
SOLUTION
This question is a perfect example of how heap data structure can be utilized in solving a question that requires greedy approach
In this case, everytime you have to add the smallest two numbers.You can even do this question using a auxillary array that will store all the prefix sums
but here we will be utilizing an heap to do so
ALGORITHM
1.Make a min heap
2.Push all the elements in the heap
3.Remove top two elements from the heap and store its sum in another variable
4.Push this sum again in the heap
5.Continue till heap is empty

from heapq import *
def connectRopes(ropeLengths):
    minHeap = []
    for length in ropeLengths: #push all the lengths in heap
        heappush(minHeap, length)

    finalLength = 0
    while len(minHeap) > 1:
        temp = heappop(minHeap) + heappop(minHeap) #pop the first two elements
        finalLength += temp #Calculate its sum and store in another variable 
        heappush(minHeap, temp) #Push the current sum again in heap for further calculations
    return finalLength

Time Complexity
Inserting all the elements inside a heap will take O(NlogN)
Removing top two elements and again push in heap will take a maximum of O(NlogN) time
So overall time complexity is O(NlogN)
Space Complexity
minHeap will require a space of O(N)

How to start Leetcode grind

Riyaz — Fri, 11 Feb 2022 17:55:40 +0000

Since you have click on this blog i may assume you are a complete beginner in leetcode and want to start your leetcode journey to get into top tech companies or change companies.

By leetcode grind , I do not recommened only using leetcode but also other websites such as GeeksForGeeks, HackerRank etc. to get more exposure to different questions.

But before you jump into solving questions of any type I recommend you to understand how the Data Structures are implemented and some theory around them.After thats down lets move on to actual coding.

You might have heard of many patterns of programming like Blind75, Sean Prashad, Grokking the coding interview etc which are great(I use them too) but only doing that questions but guarantee you get good in coding.These questions cover all the patterns that are important but only doing them will not guarantee you can do all the similar questions related to them.

For Example, Lets say you are solving questions on binary Trees and you come across the Depth First Search of Binary Tree.Now you know how to do a level order traversal but you might not always be able to solve all the questions around Depth First Search unless you have solved plenty of them.For example, lets say the question is

Q.)Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum.

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Lets say you know this question requires you to use DFS but how are you going to store the individual values of all the node and sum them to find if they are equal to targetSum.

For a complete beginner it may not come handy unless you have practiced a lot of such questions.

Now in the iterative version of DFS you know that you have to use stack to remember visited nodes and traverse further.So you are aware that stack is used to store the nodes.So instead of storing only the nodes in the stack you can also store a tuple inside the stack along with the node’s sum of all the previous node value.Something like this

This little trick is hard to come up with your own,but once you know it you can solve many questions regarding the DFS of Binary Tree i.e now you know that you can use the stack itself to store more data about the binary tree.

def pathSum(root):
    if not root: return None
    stack = [(root,root.val,[root.val])]
    ans = []
    while stack:
        node,val,li = stack.pop()
        if not node.left and not node.right and val == targetSum:
            ans.append(li)
        if node.right:
            stack.append((node.right,val+node.right.val,li+[node.right.val]))
        if node.left:
            stack.append((node.left,val+node.left.val,li+[node.left.val]))

    return ans

This trick of storing using tuples in stack will help you solve a lot more questions.

So my point is after reading one pattern, solve as many questions related to it as you can.Another important thing to consider is to not give a question more than 5–7 minutes of your time in the beginning for easy questions.The reason for it is if you can’t come up with a solution for easy question in 5 minutes then maybe you are lacking some concepts regarding it.

One more important thing to remember is spaced repetition.You might not remember everything you do.So it is better to revise them from time to time to completely grasp the concept or the question.

Some Motivation
‘‘The reason to win the game is so that you can be free of it.’’ — Naval Ravikant
HAPPY GRINDING