After several months of rehearsal, the cows are just about ready to put on their annual dance performance; this year they are performing the famous bovine ballet “Cowpelia”. The only aspect of the show that remains to be determined is the size of the stage. A stage of size K can support K cows dancing simultaneously. The N cows in the […]
Category: Algorithm
1477. Find Two Non-overlapping Sub-arrays Each With Target Sum
Given an array of integers arr and an integer target. You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum. Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two […]
Cut Ribbon
Given an array of integers with elements representing lengths of ribbons. Your goal is to obtain k ribbons of equal length cutting the ribbons into as many pieces as you want. Find the maximum integer length L to obtain at least k ribbons of length L. Example 1: First, we will find the largest length of ribbon, as we […]
Leetcode – 23. Merge k Sorted Lists
You are given an array of k arrays/linked-lists arrays, each array/linked-list is sorted in ascending or descending order. Merge all the arrays/linked-lists into one sorted array/linked-list and return it. Example 1: Input: arrays= [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The arrays/linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted array/list: 1->1->2->3->4->4->5->6 Constraints: k == arrays.length 0 <= […]
Important and Useful links from all over the Leetcode
List of all good posts on Leetcode. Comment down whichever I am missing and I will add all of them here – DP for beginners by @wh0ami – https://leetcode.com/discuss/general-discussion/662866/dp-for-beginners-problems-patterns-sample-solutions[LIST – https://leetcode.com/list/x1k8lxi5] Graph for beginners by @wh0ami – https://leetcode.com/discuss/general-discussion/655708/graph-for-beginners-problems-pattern-sample-solutions/562734[LIST – https://leetcode.com/list/x1wy4de7] Sliding window for beginners by @wh0ami – https://leetcode.com/discuss/general-discussion/657507/sliding-window-for-beginners-problems-template-sample-solutions/562721[LIST – https://leetcode.com/list/x1lbzfk3] DP Patterns by @aatalyk – https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns Leetcode patterns from edu_cative_dot_io by @late_riser […]
Leetcode – 78. Subsets
Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Solution: Cascading Approach: Lets say, we have a set S={1,2,3,4}. Pick an element from set, ex. 4, now you have 2 sets – {[], [4]}. Now pick the second element from list ex. 3, now you […]
Leetcode – 117. Populating Next Right Pointers in Each Node II
Given a binary tree 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: Input: {“$id”:”1″,”left”:{“$id”:”2″,”left”:{“$id”:”3″,”left”:null,”next”:null,”right”:null,”val”:4},”next”:null,”right”:{“$id”:”4″,”left”:null,”next”:null,”right”:null,”val”:5},”val”:2},”next”:null,”right”:{“$id”:”5″,”left”:null,”next”:null,”right”:{“$id”:”6″,”left”:null,”next”:null,”right”:null,”val”:7},”val”:3},”val”:1} Output: {“$id”:”1″,”left”:{“$id”:”2″,”left”:{“$id”:”3″,”left”:null,”next”:{“$id”:”4″,”left”:null,”next”:{“$id”:”5″,”left”:null,”next”:null,”right”:null,”val”:7},”right”:null,”val”:5},”right”:null,”val”:4},”next”:{“$id”:”6″,”left”:null,”next”:null,”right”:{“$ref”:”5″},”val”:3},”right”:{“$ref”:”4″},”val”:2},”next”:null,”right”:{“$ref”:”6″},”val”:1} Explanation: Given […]
Leetcode – 968 – Binary Tree Cameras
Given a binary tree, we install cameras on the nodes of the tree. Each camera at a node can monitor its parent, itself, and its immediate children. Calculate the minimum number of cameras needed to monitor all nodes of the tree. Example 1: Input: [0,0,null,0,0] Output: 1 Explanation: One camera is enough to monitor all nodes if placed […]
Leetcode 99 – Recover Binary Search Tree – Constant space
Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure with constant space. Example 1: Input: [1,3,null,null,2] 1 / 3 \ 2 Output: [3,1,null,null,2] 3 / 1 \ 2 Example 2: Input: [3,1,4,null,null,2] 3 / \ 1 4 […]
Leetcode 685 – Redundant Connection II
In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents. The given input is a directed graph that started as a rooted […]