Problem Given an array of integers nums, sort the array in ascending order. You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible. Examples Input: Array of numbers , unsorted. Eg. ...
Problem 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. ...
Problem Given a Linked List, Sort it using merge sort. Examples Example 1: Input: head = [4,2,1,3] Output: [1,2,3,4] Solution Method 1 - Recursive Refer merge sort - Merge Sort Algorithm. Get the pointer to middle node Split the list at the middle node Continue 1 and 2 , till list size is 1 or 2. Sort the elements in step 3 Merge the sorted list Now this involves 2 problems - Middle of the linked list Problem and Merge Two Sorted Linked Lists. To split linked list into 2, we can also use: Split Linked List into two halves fractionally given n ...
Problem Given an array of integer write an algorithm to find 3 elements that sum to a zero. In short a+b+c = 0. OR Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. ...
Problem Given an array of integer write an algorithm to find 3 elements that sum to a given number k. In short a+b+c = k. Example Example 1: Input: nums= [3,1,7,4,5,9,10] , k = 21; Output: [ [7, 4, 10] ] Follow up What if Duplicates Not Allowed? Solution Method 1 - Brute Force Use 3 nested loops and find the 3 elements which sum to k. ...
Problem Given a list of intervals representing the start and end time of ‘N’ meetings, find the minimum number of rooms required to hold all the meetings. Examples Example 1: Meetings: [ [1,4], [2,5], [7,9] ] Output: 2 Explanation: Since [1,4] and [2,5] overlap, we need two rooms to hold these two meetings. [7,9] can occur in any of the two rooms later. ...
Problem Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings. Please implement encode and decode Examples Example1 Input: ["lint","code","love","you"] Output: ["lint","code","love","you"] Explanation: One possible encode method is: "lint:;code:;love:;you" ...
Problem 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]. Examples 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] Constraints 2 <= nums.length <= 105 -30 <= nums[i] <= 30 The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. Follow up Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.) ...
Problem Find all valid combinations of k numbers that sum up to n such that the following conditions are true: Only numbers 1 through 9 are used. Each number is used at most once. Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order. Examples Example 1: Input: k = 3, n = 7 Output: [ [1,2,4] ] Explanation: 1 + 2 + 4 = 7 There are no other valid combinations. ...
Problem A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise. Examples Example 1: ...