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 Given two strings s and t, return true if s is a subsequence of t, or false otherwise. OR Given two strings str1 and str2, find if str1 is a subsequence of str2. Subarrays vs Subsequences vs Subsets Definition Follow up Expected time complexity is linear. Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code? Examples Example 1: ...
Problem Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Definition Majority Element: If an element appears more than n/2 times in array where n is the size of the array. Examples int [] arrA = {1,3,5,5,5,5,4,1,5}; Output: Element appearing more than n/2 times: 5 int []arrA = {1,2,3,4}; Output: No element appearing more than n/2 times ...
Problem Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct. Examples Example 1: Input: nums = [1,2,3,1] Output: true Example 2: Input: nums = [1,2,3,4] Output: false ...
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 ...
Problem Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Examples Example 1: Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 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 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. ...