Given a collection of numbers that might contain duplicates, return all possible unique permutations in C++
Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] In my pervious post we have discussed three solutions where the numbers are unique. Recommend to read that post before proceeding to this. Given a collection of distinct integers, return all possible permutations. This problem can also be solved in 4 different ways. Namely: 1. Backtracking […]
Given a collection of distinct integers, return all possible permutations.
Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] The solution for this problem can be solved in 2 ways: 1. Using recursion 2. Using next permutation. 3. Using Heap’s algorithm < https://en.wikipedia.org/wiki/Heap%27s_algorithm> First we shall look at the code, later I shall explain about the working of all three the solutions […]
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1: Input: num1 = "2", num2 = "3" Output: "6" Example 2: Input: num1 = "123", num2 = "456" Output: "56088" Note: 1. The length of both num1 and num2 is < 110. 2. Both num1 and num2 contain only digits 0-9. 3. Both num1 and num2 do not contain any leading zero, except […]
Given a collection of candidate numbers and a key, find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination. Note: • All numbers (including target) will be positive integers. • The solution set must not contain duplicate combinations. Example 1: Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] […]
Merge k sorted linked lists and return it as one sorted list in C++
Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 This problem can be solved by below given ways: 1. Using Map 2. Using merge Sort or Divide and Conquer 3. Using Recursive 4. Using Priority Queue Here we shall discuss about 2 solutions 1. Using merge sort or Divide and Conquer 2. Using Recursive Before […]
Given an array sorted in ascending order and is rotated at some pivot, given a target value to search, if found in the array return its index
Problem explanation: Initial Sorted array: [0,1,2,4,5,6,7] After rotation it becomes [4,5,6,7,0,1,2]. Target = 0 Index = 4 [as array index starts from 0] This problem can be solved by 2 ways: 1. Linear Search 2. Modified Binary search 1. Linear search: In this solution we search the element one by one, and return the index. […]
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). Examples: Input -> output 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 Problem explanation: Given a number, find the next highest number, using the same digits given in the array. For example: 1234 -> […]
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero. Example 1: Input: dividend = 10, divisor = 3 Output: 3 Example 2: Input: dividend = 7, divisor = -3 Output: -2 • Both dividend and divisor will be 32-bit signed integers. • The divisor will never be 0. • […]
Swap Nodes in Pairs solution in C
Given a linked list, swap every two adjacent nodes and return its head. Example: Given 1->2->3->4, you should return the list as 2->1->4->3. Note: • Your algorithm should use only constant extra space. • You may not modify the values in the list’s nodes, only nodes itself may be changed. We can solve the above […]
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Note: 1. Need merged elements in a new list, not in the existing list. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4 The solution as expected is very simple. In this tutorial we shall look at 2 different solutions: 1. Iterative Method 2. Recursion Method For both the solution the concept will remain the same as explained […]