Subsets II in CPP
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Example: Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] Before solving this problem, have a look at similar kind of problem Subsets. Given a collection of […]
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. Example 1: Input: 2 Output: [0,1,3,2] Explanation: 00 – 0 01 – 1 11 – 3 10 – 2 For a given n, a gray code sequence […]
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions. Example: Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5 Solution: Let us understand the question first. The question has 2 parts: Part 1: Here we need to partition the list in such a way that the nodes less […]
Remove Duplicates from Sorted List solution in CPP
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1: Input: 1->2->3->3->4->4->5 Output: 1->2->5 Example 2: Input: 1->1->1->2->3 Output: 2->3 Solution: For the solution we take 2 nodes a “dummy” node and a “current” node. Use “dummy” node, incase if head is needed […]
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]). You are given a target value to search. If found in the array return true, otherwise return false. Example 1: Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true Example 2: Input: nums = [2,5,6,0,0,1,2], target = 3 Output: false Before solving this problem, please look at the similar problem. […]
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. Example 1: Given nums = [1,1,1,2,2,3], Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It doesn’t matter what you […]
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. 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: Input: 4 Output: [ [".Q..", // Solution 1 "…Q", "Q…", "..Q."], ["..Q.", // Solution 2 "Q…", "…Q", ".Q.."] […]
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighbouring. The same letter cell may not be used more than once. Example: board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] Given word = “ABCCED”, return true. Given word = “SEE”, return true. Given word = “ABCB”, […]
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] The problem can be solved in 2 ways: 1. Iterative 2. Backtracking Solution 1: Iterative Solution. In this solution, we take 2 loops, outer loop and inner loop. Then we […]
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
Example: Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] This problem can be solved in 2 ways. 1. Iterative 2. Recursion/Backtrack In the iterative solution, we take a temp array of size “k”. Then we move to the right index, and start filling the values in that […]