Leetcode

This is one of the solution for Kth Largest Element in an Array. We have already understood the problem here - Kth Smallest Element Using Randomized Selection. Pivot at the end public int findKthLargest(int[] nums, int k) { return quickSelect(nums, nums.length - k + 1, 0, nums.length - 1); } int quickSelect(int[] nums, int k, int start, int end) { int pivot = nums[end]; int left = start; int right = end; while (true) { while (nums[left] < pivot && left < right) { left++; } while (nums[right] >= pivot && right > left) { right--; } if (left == right) { break; } swap(nums, left, right); } swap(nums, left, end); if (k == left + 1) { return pivot; } else if (k < left + 1) { return quickSelect(nums, k, start, left - 1); } else { return quickSelect(nums, k, left + 1, end); } } void swap(int[] A, int i, int j) { int tmp = A[i]; A[i] = A[j]; A[j] = tmp; } ...

Problem Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself. Examples Example 1: ...

Problem Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". OR Given a sentence, give Longest Sequence Of Prefix Shared By All The Words In A String Longest common prefix for a pair of strings S1 and S2 is the longest string S which is the prefix of both S1 and S2. ...

Problem Find the minimum element in the rotated sorted array. For example, the array a = [0, 1, 2, 4, 6, 8, 10] might become: [8, 10, 0, 1, 2, 4, 6] if it was rotated 2 times. [4, 6, 8, 10, 0, 1, 2] if it was rotated 4 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]]. ...

Problem Given an m x n matrix of 0s and 1s, provide an algorithm such that if an element is 0, its entire row and column is set to 0 OR Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s. You must do it in place. Follow Up: Can you do it in one pass? ...

Problem Given a circular linked list, implement an algorithm which returns node at the beginning of the loop. If there is no cycle, return null. Try solving it using constant additional space. Definition - Circular Linked List A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list. This is extension of Linked List Cycle 1 - Detect Cycle ...

Problem You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin. ...

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 Given a sorted array arr[] of n elements, write a function to search a given element x in arr[]. Input: A sorted array, arrA[] and an key Output : Return index if element is found, else -1. Examples Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4 ...

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