Problem Given a string s, return the longest palindromic substring in s. Incase of conflict, return the substring which occurs first ( with the least starting index ). Substring of string S: S[i...j] where 0 <= i <= j < len(S) Example Example 1: Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer. ...
Problem Given a set of distinct integers/characters, S, return all possible subsets. OR Given an integer array nums of unique elements, return all possible subsets (the power set). Examples If we’re given a set of integers such that S = {1, 2, 3}, how can we find all the subsets of that set? For example, given S, the set of all subsets i.e. P(S) we get are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}. Here is {} is empty set denoted by Φ. ...
Problem Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer. The algorithm for myAtoi(string s) is as follows: Whitespace: Ignore any leading whitespace (" "). Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity is neither present. Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0. Rounding: If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then round the integer to remain in the range. Specifically, integers less than -2^31 should be rounded to -2^31, and integers greater than 2^31 - 1 should be rounded to 2^31 - 1. Return the integer as the final result. ...
Problem Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree. Examples Example 1: 3 / \ / \ 1 4 \ / \ / 2 ...
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 an array arr[], find the maximum j – i such that arr[j] > arr[i]. Examples Example 1: Input: {34, 8, 10, 3, 2, 80, 30, 33, 1} Output: 6 (j = 7, i = 1) Example 2: Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0} Output: 8 ( j = 8, i = 0) ...
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. ...