DEV Community: Drj

Leetcode: 598.Range Addition II

Drj — Mon, 30 Aug 2021 17:11:12 +0000

Problem statement

You are given an m x n matrix M initialized with all 0's and an array of operations ops, where ops[i] = [ai, bi] means M[x][y] should be incremented by one for all 0 <= x < ai and 0 <= y < bi.

Count and return the number of maximum integers in the matrix after performing all the operations.

Example 1:
Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

Example 2:
Input: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]
Output: 4

Example 3:
Input: m = 3, n = 3, ops = []
Output: 9

Constraints:

1 <= m, n <= 4 * 104
1 <= ops.length <= 104
ops[i].length == 2
1 <= ai <= m
1 <= bi <= n

Idea

The problem statement says that we will be given a matrix and an array of matrix cell positions , we need to increment the count of all the cells from (0,0) to each matrix cell position. After completing all these operations we need to find out the count of maximum integer in the matrix.

So , the question is to find out the count of the maximum integer after performing all the given operations.

As per the question , a cell (x , y) value can be incremented if and only if (x , y) is one of the cell from (0,0) to the given input (p , q).

So , the maximum integer will be produced when matrix cell value is incremented more number of times.

For a matrix cell to be maximum value , we need to figure out the most overlapping cell between the given set of operations/matrix cell positions as the range of cells which overlaps the most will get chance to increment more number of times.

If you look at the first example , in first operation each cell value is incremented from (0,0) to (2,2) , in second operation each cell from (0,0) to (2,2) again got incremented as it overlaps with (3,3).

So , solution is to simple find out the product of minimum of first co-ordinates of cell and minimum of second co-ordinates of cell.

We are taking product because we need to find out the count of the maximum integer in the matrix after performing all the given operations.

Code-Python

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        length = len(ops)
        if length == 0:
            return m*n
        result = [ops[0][0] , ops[0][1]]
        for i in range(1,length):
            result[0] = min(result[0] , ops[i][0])
            result[1] = min(result[1] , ops[i][1])
        return result[0]*result[1]

Link to the question on leetcode

Below git repo contains some important programming questions and solution from leetcode and interviewbit

dheerajthodupunoori / problem-solving

Problem solving questions and solutions.

Problem Solving

This repository contains some of important data structures and algorithm questions which are important for any product-based company interviews.

Currently , this repository contains few questions on graph data structure and linked-list. Will be adding more shortly.

Please feel free to contribute to this repository.

View on GitHub

Leetcode : 521. Longest Uncommon Subsequence I

Drj — Fri, 27 Aug 2021 15:52:16 +0000

Problem Statement

Given two strings a and b, return the length of the **longest uncommon subsequence* between* a and b. If the longest uncommon subsequence does not exist, return -1.

An uncommon subsequence between two strings is a string that is a subsequence of one but not the other.

A subsequence of a string s is a string that can be obtained after deleting any number of characters from s.

For example, "abc" is a subsequence of "aebdc" because you can delete the underlined characters in "aebdc" to get "abc". Other subsequences of "aebdc" include "aebdc", "aeb", and "" (empty string).

Example 1:

Input: a = "aba", b = "cdc"
Output: 3
Explanation: One longest uncommon subsequence is "aba" because "aba" is a subsequence of "aba" but not "cdc".
Note that "cdc" is also a longest uncommon subsequence.

Example 2:

Input: a = "aaa", b = "bbb"
Output: 3
Explanation: The longest uncommon subsequences are "aaa" and "bbb".

Example 3:

Input: a = "aaa", b = "aaa"
Output: -1
Explanation: Every subsequence of string a is also a subsequence of string b. Similarly, every subsequence of string b is also a subsequence of string a.

Constraints:

1 <= a.length, b.length <= 100
a and b consist of lower-case English letters.

Idea

Brute Force Solution: Generate all the subsequences of both the strings and store the frequency of each subsequence in a hashmap/dictionary. The subsequence whose frequency equal to 1 will be the longest uncommon subsequence. If there is not subsequence with frequency as 1 , then there is no uncommon subsequence for given strings.

Optimized Solution:

If both the given strings are equal then there will not be uncommon subsequences for given strings. In this case we can directly return -1

If the strings are not equal and length of both the strings are equal , then one string cannot be the subsequence of other string. In this case we can either return length of any one of the strings.

If both strings are not equal and length of one string is greater than length of other string, then in this case we can directly return the length of the largest string as the largest string cannot be the subsequence of the smaller string.

Code(Python)

class Solution:
    def findLUSlength(self, a: str, b: str) -> int:
        if a == b:
            return -1
        a_length = len(a)
        b_length = len(b)
        return max(a_length,b_length)

Below git repo contains some important programming questions and solution from leetcode and interviewbit

dheerajthodupunoori / problem-solving

Problem solving questions and solutions.

Problem Solving

This repository contains some of important data structures and algorithm questions which are important for any product-based company interviews.

Currently , this repository contains few questions on graph data structure and linked-list. Will be adding more shortly.

Please feel free to contribute to this repository.

View on GitHub

Leetcode : Search a 2D Matrix II

Drj — Thu, 26 Aug 2021 16:42:44 +0000

Problem statement

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example:1

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5

Output: true

Example:2

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20

Output: false

Constraints

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matix[i][j] <= 109
All the integers in each row are sorted in ascending order.
All the integers in each column are sorted in ascending order.
-109 <= target <= 109.

Link to the question on Leetcode

Idea

Bruteforce solution : The bruteforce solution for this problem is directly checking each cell of the matrix and return True if target is found or else return False.

Time complexity : O(M*N) , M = number of rows , n = number of columns.

Optimized solution for this problem is, as per the problem statement rows and columns are sorted from left to right and top to bottom , we can directly do binary search on each row.

Time complexity : O(M logN) , M = number of rows , n = number of columns.

We can still optimize this solution to O(M+N).Lets discuss that solution with below example.

Lets initialize two variables i and j as first row and last column as below.

Since target is less the current cell we move to the left in the matrix (as rows and columns are sorted from left to right and top to bottom)

Since target is greater than current cell value we move to the next row.

Since target is still greater than the current cell value , we again move down the matrix.

Now target is less than the current cell value , so we move towards the left of the matrix within the current row.

Now target is greater than the current cell value , so we move down the matrix within the same column.

Now target is less than the current cell value , so we move to the left of the matrix within the current row.

At this point , we got cell whose value is equal to target , so we return True

So the overall idea here is whenever we encounter a cell whose value is greater than target we move towards the left within the same row having said that columns are sorted from top to bottom (so we are sure that we will not get the target element if move down the matrix , so we move to the left) and whenever we encounter a cell whose value is less than the target we move down the matrix as rows are sorted from left to right(as we can guarantee that moving left will not give us the target element).

Code - Python

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])
        i = 0
        j = cols-1
        while i >= 0 and j >= 0 and i < rows:
            cell_value = matrix[i][j]
            if cell_value == target:
                return True
            elif cell_value > target:
                j -= 1
            else:
                i += 1
        return False

Please like this post if you found this informative.

Two Sum IV - Input is a BST

Drj — Mon, 23 Aug 2021 11:58:37 +0000

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Approach

This question is similar to finding if their are two elements in an array such that their sum is equal to the given target.

This problem can be solved either using BFS or DFS. We will solve this using level order traversal(BFS) which uses queue data structure for tree traversing.

The idea here is initialize an empty set , for every node check if target-node.value is available in set , if it is available return True , else add that node value to the set.

At the end directly return False as there is no such elements present in BST.

The reason why I have chosen set for storing the node values is , insert and retrieve operations on set can be done in O(1) time complexity as internally set is implemented using Hashing.

Code

from collections import deque
# 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
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        queue = deque()
        queue.append(root)
        available = set()
        while len(queue)>0:
            popped = queue.popleft()
            if k-popped.val in available:
                return True
            else:
                available.add(popped.val)
            if popped.left:
                queue.append(popped.left)
            if popped.right:
                queue.append(popped.right)
        return False

Note: If anyone want to more about level order traversal of a tree , please let me know in comments. I will write a detailed post on level order traversal.

Maximum Product of Splitted Binary Tree

Drj — Thu, 19 Aug 2021 16:18:55 +0000

Problem statement

Given the root of a binary tree, split the binary tree into two subtrees by removing one edge such that the product of the sums of the subtrees is maximized.

Return the maximum product of the sums of the two subtrees. Since the answer may be too large, return it modulo 109 + 7.

Note that you need to maximize the answer before taking the mod and not after taking it.

Link to the question on Leetcode

Example:1

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

Approach

The question says that we have to split the binary tree to sub tree where the product of sum of two subtrees are maximized. Splitting the binary tree means removing one edge from binary tree.

We can solve this problem by pre calculating the sum of subtree for each node which will help us in finding the maximum product of sum of sub trees.

So the idea here is we have to find out the maximum value of subtree multiplied with total tree sum minus subtree sum which gives the product of sum of subtrees.

Lets solve this with example [2,3,9,10,7,8,6,5,4,11,1]. This is the given tree. Below is the tree representation of above input.

First lets calculate the sum of subtree for each node. Sum of all the subtrees are as below:

Now lets try to remove the edge between root node "2" and its left child "3" , we get two subtrees . we can get the sum of two subtrees directly from our pre calculated values . The sum of two subtrees can be calculated as in below image.

We can directly get the sum of subtree1 from our pre calculated values and sum of other subtree will total tree sum minus subtree1 sum. Find the product of these two subtrees.

In the same way we have to try removing all the edges one by one and find the maximum product of sum of subtrees.

Note:To pre calculate all the subtrees sum use post order traversal of binary tree and store all the values in a dictionary.

Code

import math

# 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
class Solution:
    def maxProduct(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        subtree_sum = dict()
        self.subtree_sum(root,subtree_sum)
        root_subtree_sum = subtree_sum[root]
        maximum = 0
        for subtree in subtree_sum:
            maximum = max(maximum , subtree_sum[subtree] * (root_subtree_sum - subtree_sum[subtree]))
        return int(maximum%(math.pow(10,9)+7))

    def subtree_sum(self,root,subtree_sum):
        if root is None:
            return
        self.subtree_sum(root.left,subtree_sum)
        self.subtree_sum(root.right,subtree_sum)
        left_sum = 0
        right_sum = 0
        if root.left:
            left_sum = subtree_sum.get(root.left)
        if root.right:
            right_sum = subtree_sum.get(root.right)
        subtree_sum[root] = left_sum + right_sum + root.val

August leetcoding challenge - Count Good Nodes in Binary Tree

Drj — Tue, 17 Aug 2021 12:31:13 +0000

Problem Statement

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Example:1

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Approach

The problem statement says that , we have to find out the number of good nodes in a given binary tree where a node is called good node if in the path from root to the node , there is no greater value than the current node.

So the idea here is , we can say a node to be a good node by comparing the current node value with the value that is maximum from root to current node. If current node value is greater than the maximum we can consider the current node as good node.

Now the problem boils down to keeping track of the maximum value from root to any node "x".

We can solve this problem iteratively using level order traversal of a binary tree.

Pseudo code

We will be using level order traversal of a binary tree to solve this problem. Level order traversing of a tree is nothing but traversing the tree level by level.

Initialize a count variable and queue to keep track of the nodes of the tree.
Append root node and root node value as a tuple to the queue . In this tuple first element represents the node and second element represents the maximum value seen from root to this node(keeping track of maximum value for comparision)
Follow below steps until queue is empty:

Pop the item (node,maximum) from the queue - where each item in queue represents the the node and the maximum value have till now from root to node

check if the node value is greater than the maximum . If yes increment the count by 1

If node has the left child - append left child to the queue along with maximum value seen till now from root node to the current node.left

If node has the right child - append the right child to the queue along with the maximum value seen till now from root node to the current node.right.

Return count once queue is empty - queue empty represents that we have visited all the nodes of the binary tree.

code

from collections import deque

# 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
class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        if root is None:
            return 0
        count = 0
        queue = deque()
        queue.append((root,root.val))
        while len(queue)>0:
            popped,value = queue.popleft()
            if popped.val >= value:
                count+=1
            if popped.left:  
             queue.append((popped.left,max(popped.left.val,value)))
            if popped.right:   
           queue.append((popped.right,max(popped.right.val,value)))
        return count

Open for any discussions!

August leetcoding Challenge 2021 - Range Sum Query - Immutable

Drj — Mon, 16 Aug 2021 17:20:01 +0000

Given an integer array nums, handle multiple queries of the following type:

Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.
Implement the NumArray class:

NumArray(int[] nums) Initializes the object with the integer array nums.
int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) > = -3

Link to question on leetcode

Bruteforce approach

The bruteforce solution for this question would , when ever a sumRange query is called compute the sum from given start and end index and return the sum.

Time complexity for this approach will be O(number of time function called * n) - here we are computing the sum for every query

Optimized solution

Instead of calculating the sum for every query , we can have a precomputed sum array , where prefix[i] will be the sum of array from 0 to i . Using this precomputed array for every query we can return the sum in O(1) time complexity.

Psuedo code

Created a prefix array of size of the given array.

Compute the prefix array where prefix[i] will give the sum of array from 0 to i(inclusive)

Now for every query requested , do the following:

If left is 0 , directly return prefix[right]

else return prefix[right] - prefix[left-1] - because prefix of right will be sum of original array from 0 to right , so we have to substract sum of array from 0 to left-1 from prefix[right]

Code

class NumArray:
    def __init__(self, nums: List[int]):
        self.length = len(nums)
        self.prefixsum = [0]*self.length
        self.prefixsum[0] = nums[0]
        for i in range(1,self.length):
            self.prefixsum[i] = self.prefixsum[i-1]+nums[i]
        self.total = self.prefixsum[-1]


    def sumRange(self, left: int, right: int) -> int:
        if left == 0:
            return self.prefixsum[right]
        return self.prefixsum[right]-self.prefixsum[left-1]

Please like this post and share if you found this post helpful.

DEV Community: Drj

Leetcode: 598.Range Addition II

dheerajthodupunoori / problem-solving

Problem solving questions and solutions.

Problem Solving

Leetcode : 521. Longest Uncommon Subsequence I

dheerajthodupunoori / problem-solving

Problem solving questions and solutions.

Problem Solving

Leetcode : Search a 2D Matrix II

Bruteforce solution : The bruteforce solution for this problem is directly checking each cell of the matrix and return True if target is found or else return False.

Time complexity : O(M*N) , M = number of rows , n = number of columns.

Time complexity : O(M logN) , M = number of rows , n = number of columns.

Two Sum IV - Input is a BST

Maximum Product of Splitted Binary Tree

August leetcoding challenge - Count Good Nodes in Binary Tree

August leetcoding Challenge 2021 - Range Sum Query - Immutable