snowscriptwinterofcode/leetcode_q

Solve with us the most mind boggling DSA questions to ace your skills

leetcode_q's Issues

Day-1 q1: Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Day-1 q3: First and last occurrences of x

Given a sorted array arr containing n elements with possibly some duplicate, the task is to find the first and last occurrences of an element x in the given array.
Note: If the number x is not found in the array then return both the indices as -1.

Example 1:

Input:
n=9, x=5
arr[] = { 1, 3, 5, 5, 5, 5, 67, 123, 125 }
Output:
2 5
Explanation:
First occurrence of 5 is at index 2 and last occurrence of 5 is at index 5.

1531. String Compression II

Hi, I want to add this question to this repository along with its solution. Kindly assign this to me 1531. String Compression II

Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

1. The number of nodes in the tree is in the range [2, 105].
2. -109 <= Node.val <= 109
3. All Node.val are unique.
4. p != q
5. p and q will exist in the tree.

724. Find Pivot Index

I want to contribute to the repo by adding this question as well as its solution.
Kindly assign me this. @bh-g
https://leetcode.com/problems/find-pivot-index/description/

Day-4 q2: Minimum Number of Flips

Given a binary string, that is it contains only 0s and 1s. We need to make this string a sequence of alternate characters by flipping some of the bits, our goal is to minimize the number of bits to be flipped.

Example 1:

Input:
S = "001"
Output: 1
Explanation: We can flip the 0th bit to 1 to have 101.

Example 2:

Input:
S = "0001010111"
Output: 2
Explanation: We can flip the 1st and 8th bit bit to have "0101010101"

Reverse Linked List

Hi, I want to add this question to this repository along with its solution. Kindly assign this to me
Reverse Linked List

162. Find Peak Element

I want to contribute to the repo by adding this question as well as its solution.
Kindly assign me this. @bh-g
https://leetcode.com/problems/find-peak-element/description/

N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

Constraints:
1 <= n <= 9

1335. Minimum Difficulty of a Job Schedule

Hi, I want to add this question to this repository along with its solution. Kindly assign this to me1335. Minimum Difficulty of a Job Schedule

Asteroid Collision

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Constraints:

1. 2 <= asteroids.length <= 104
2. -1000 <= asteroids[i] <= 1000
3. asteroids[i] != 0

Product Of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

Write an algorithm that runs in O(n) time and without using the division operation.

I want to add this question and its solution in the repository. @bh-g Please assign this issue to me.

Container With Most Water

Hi, I want to add this question to this repository along with its solution. Kindly assign this to me
Container With Most Water

48. Rotate Image

I want to contribute to the repo by adding this question as well as its solution.
Kindly assign me this. @bh-g
https://leetcode.com/problems/rotate-image/description/

Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.
Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

I would like to include this question in the repository, along with its solution. Please assign me this task. Thank you. @bh-g

D2Q1

Problem
Example

Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighbouring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

1. m == board.length
2. n = board[i].length
3. 1 <= m, n <= 6
4. 1 <= word.length <= 15
5. board and word consists of only lowercase and uppercase English letters.

Day-3 q2: Unbounded Knapsack

Problem statement

You are given ‘n’ items with certain ‘profit’ and ‘weight’ and a knapsack with weight capacity ‘w’.

You need to fill the knapsack with the items in such a way that you get the maximum profit. You are allowed to take one item multiple times.

Example:
Input:
'n' = 3, 'w' = 10,
'profit' = [5, 11, 13]
'weight' = [2, 4, 6]

Output: 27

Explanation:
We can fill the knapsack as:

1 item of weight 6 and 1 item of weight 4.
1 item of weight 6 and 2 items of weight 2.
2 items of weight 4 and 1 item of weight 2.
5 items of weight 2.

The maximum profit will be from case 3 = 11 + 11 + 5 = 27. Therefore maximum profit = 27.

Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1:
3 15
7 2 4
5 10 20

Expected Answer:
21

Output on console:
21

Explanation of Sample Input 1
The given knapsack capacity is 15. We can fill the knapsack as [1, 1, 1] giving us profit 21 and as [1,2] giving us profit 9. Thus maximum profit will be 21.

Sample Input 2
2 3
6 12
4 17

Expected Answer:
0

Output on console:
0

Explanation of Sample Input 2:
We can clearly see that no item has weight less than knapsack capacity. Therefore we can not fill knapsack with any item.

Expected Time Complexity:
Try to solve this in O(n*w).

Constraints
1 <= n <= 10^3
1 <= w <= 10^3
1 <= profit[i] , weight[i] <= 10^8

Time Limit: 1 sec

189. Rotate Array

I want to contribute to the repo by adding this question as well as its solution.
Kindly assign me this. @bh-g
https://leetcode.com/problems/rotate-array/description/

Day-2 q1: Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array

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.

NOTE: 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.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

1. n == nums.length
2. 1 <= n <= 5000
3. -5000 <= nums[i] <= 5000
4. All the integers of nums are unique.
5. nums is sorted and rotated between 1 and n times.

Search in Rotated Sorted Array

Hi, I want to add this question to this repository along with its solution. Kindly assign this to me
Search in Rotated Sorted Array

303. Range Sum Query - Immutable

I want to contribute to the repo by adding this question as well as its solution.
Kindly assign me this. @bh-g
https://leetcode.com/problems/range-sum-query-immutable/description/

304. Range Sum Query 2D - Immutable

I want to contribute to the repo by adding this question as well as its solution.
Kindly assign me this. @bh-g
https://leetcode.com/problems/range-sum-query-2d-immutable/description/

Linked List Cycle

Hi, I want to add this question to this repository along with its solution. Kindly assign this to me
Linked List Cycle

Read me is not explaining exactly in which folder work is to be done

I can update the read to me to explain the folders. Please assign this issue to me

1578. Minimum Time to Make Rope Colorful

Hi, I want to add this question to this repository along with its solution. Kindly assign this to me @bh-g 1578. Minimum Time to Make Rope Colorful

Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

Example 1:
Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:
Input: nums = [3,3,7,7,10,11,11]
Output: 10

Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 105

53. Maximum Subarray

I want to contribute to the repo by adding this question as well as its solution.
Kindly assign me this. @bh-g
https://leetcode.com/problems/maximum-subarray/description/

540. Single Element in a Sorted Array

I want to contribute to the repo by adding this question as well as its solution.
Kindly assign me this. @bh-g
https://leetcode.com/problems/single-element-in-a-sorted-array/description/

House Robber

->Leetcode 198
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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

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.
Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 400

152. Maximum Product Subarray

I want to contribute to the repo by adding this question as well as its solution.
Kindly assign me this. @bh-g
https://leetcode.com/problems/maximum-product-subarray/description/

795. Number of Subarrays with Bounded Maximum

I want to contribute to this repo by adding this question as well as solution.
kindly assign me this. @bh-g
https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/description/

Populating Next Right Pointers in Each Node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:
Input: root = []
Output: []

Constraints:

1. The number of nodes in the tree is in the range [0, 212 - 1].
2. -1000 <= Node.val <= 1000

Follow-up:

1. You may only use constant extra space.
2. The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

CONCATENATION OF ARRAY

Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n (0-indexed).

Specifically, ans is the concatenation of two nums arrays.

Return the array ans.

Day-3 q3: Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:
Input: candidates = [2], target = 1
Output: []

Constraints:
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40

Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Day-2 q2: Merge Sorted Arrays

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Remove Nth Node From End of List

Hi, I want to add this question to this repository along with its solution. Kindly assign this to me
Remove Nth Node From End of List

1480. Running Sum of 1d Array

I want to contribute to the repo by adding this question as well as its solution.
Kindly assign me this. @bh-g
https://leetcode.com/problems/running-sum-of-1d-array/description/

squares of sorted array

Day-3 q1: Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints:

1. m == matrix.length
2. n == matrix[i].length
3. 1 <= m, n <= 10
4. -100 <= matrix[i][j] <= 100

Day-1 q2: Number of Pairs in an Array

Number of Pairs in an Array
Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.

A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:

0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k
Notice that |val| denotes the absolute value of val.

Example 1:

Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.
Example 2:

Input: nums = [1,2,3,4,5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

1897. Redistribute Characters to Make All Strings Equal

Hi, I want to add this question to this repository along with its solution. Kindly assign this to me 1897. Redistribute Characters to Make All Strings Equal

Count Negative Numbers in a Sorted Matrix

Problem statement

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

LeetCode Link

Day-2 q3: Length Of Last Word

Given a string s consisting of words and spaces, return the length of the last word in the string.

A word is a maximal substring consisting of non-space characters only.

Example 1:
Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

Example 2:
Input: s = " fly me to the moon "
Output: 4
Explanation: The last word is "moon" with length 4.

42. Trapping Rain Water

I want to contribute to the repo by adding this question as well as its solution.
Kindly assign me this. @bh-g
https://leetcode.com/problems/trapping-rain-water/description/

Find Smallest Letter Greater Than Target

Problem Statement
You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.

Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters.

leetcode question link

Best Time to buy and sell stock

I want to add this question to this repository along with its solution

Reorder List

Hi, I want to add this question to this repository along with its solution. Kindly assign this to me
Reorder List

Find Minimum in Rotated Sorted Array

Hi, I want to add this question to this repository along with its solution. Kindly assign this to me
Find Minimum in Rotated Sorted Array