LEETCODE SOLUTIONS

K Closest Points to Origin We have a list of points on the plane.  Find the K closest points to the origin (0, 0). (Here, the distance between two points on a plane is the Euclidean distance.) You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.) Example 1: Input: points = [[1,3],[-2,2]] , K = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]]. Example 2: Input: points = [[3,3],[5,-1],[-2,4]] , K = 2 Output: [[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.) Note: 1 <= K <= points.length <= 10000 -10000 < points[i][0] < 10000 -10000 < points[i][1] < 10000 Solution in Java: class Solution {     public int[][] k

Course Schedule There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? Example 1: Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation:  There are a total of 2 courses to take.   To take course 1 you should have finished course 0. So it is possible. Example 2: Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation:  There are a total of 2 courses to take.   To take course 1 you should have finished course 0, and to take course 0 you should   also have finished course 1. So it is impossible. Constraints: The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more

Counting Bits Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array. Example 1: Input: 2 Output: [0,1,1] Example 2: Input: 5 Output: [0,1,1,2,1,2] Follow up: It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass? Space complexity should be O(n). Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language. Solution in Java : class Solution{ public int[] countBits(int num) {     int[] result = new int[num+1];     for(int i=0; i<=num; i++){         result[i] = countEach(i);     }     return result; } public int countEach(int num){     int result = 0;     while(num!=0){         if(num%2==1){             result++;         }         num = num/2;     }     return result;

Possible Bipartition Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size. Each person may dislike some other people, and they should not go into the same group. Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group. Return true if and only if it is possible to split everyone into two groups in this way.   Example 1: Input: N = 4 , dislikes = [[1,2],[1,3],[2,4]] Output: true Explanation : group1 [1,4], group2 [2,3] Example 2: Input: N = 3 , dislikes = [[1,2],[1,3],[2,3]] Output: false Example 3: Input: N = 5 , dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]] Output: false Note: 1 <= N <= 2000 0 <= dislikes.length <= 10000 1 <= dislikes[i][j] <= N dislikes[i][0] < dislikes[i][1] There does not exist  i != j  for which  dislikes[i] == dislikes[j] . Solution in C++: class Solution { public:     bool possibl

Contiguous Array Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1. Example 2: Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1. Note:  The length of the given binary array will not exceed 50,000. Solution in java:  public class Solution {     public int findMaxLength(int[] nums) {         Map<Integer, Integer> map = new HashMap<>();         map.put(0, -1);         int maxlen = 0, count = 0;         for (int i = 0; i < nums.length; i++) {             count = count + (nums[i] == 1 ? 1 : -1);             if (map.containsKey(count)) {                 maxlen = Math.max(maxlen, i - map.get(count));             } else {                 map.put(count, i);             }         }  

Uncrossed Lines We write the integers of A and B (in the order they are given) on two separate horizontal lines. Now, we may draw connecting lines: a straight line connecting two numbers A[i] and B[j] such that: A[i] == B[j]; The line we draw does not intersect any other connecting (non-horizontal) line. Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line. Return the maximum number of connecting lines we can draw in this way. Example 1: Input: A = [1,4,2] , B = [1,2,4] Output: 2 Explanation: We can draw 2 uncrossed lines as in the diagram. We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2. Example 2: Input: A = [2,5,1,2,5] , B = [10,5,2,1,5,2] Output: 3 Example 3: Input: A = [1,3,7,1,7,5] , B = [1,9,2,5,1] Output: 2 Note: 1 <= A.length <= 500 1 <= B.length <= 500 1 <= A[i], B[i] <= 2000

Construct Binary Search Tree from Preorder Traversal Return the root node of a binary search tree that matches the given preorder traversal. (Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val.  Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.) It's guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements. Example 1: Input: [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12] Constraints: 1 <= preorder.length <= 100 1 <= preorder[i] <= 10^8 The values of preorder are distinct Solution in Java: class Solution {     public TreeNode bstFromPreorder(int[] preorder) {         if(preorder == null || preorder.length == 0){             return null;         }         Tr

Interval List Intersections Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. (Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.  The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].) Example 1: Input: A = [[0,2],[5,10],[13,23],[24,25]] , B = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists. Note: 0 <= A.length < 1000 0 <= B.length < 1000 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9 NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signat

Sort Characters By Frequency Given a string, sort it in decreasing order based on the frequency of characters. Example 1: Input: "tree" Output: "eert" Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer. Example 2: Input: "cccaaa" Output: "cccaaa" Explanation: Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer. Note that "cacaca" is incorrect, as the same characters must be together. Example 3: Input: "Aabb" Output: "bbAa" Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect. Note that 'A' and 'a' are treated as two different characters. Solution in Java : class Solution {     public String frequencySort(String s) {         in

Count Square Submatrices with All Ones Given a m * n matrix of ones and zeros, return how many square submatrices have all ones. Example 1: Input: matrix = [   [0,1,1,1],   [1,1,1,1],   [0,1,1,1] ] Output: 15 Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15 . Example 2: Input: matrix = [ [1,0,1], [1,1,0], [1,1,0] ] Output: 7 Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 + 1 = 7 . Constraints: 1 <= arr.length <= 300 1 <= arr[0].length <= 300 0 <= arr[i][j] <= 1 Solution in C++ class Solution { public:     int n,m,cnt=0;     int mat[302][302],dp[302][302];     int  dfs(int i,int j)     {         if(i>=n||j>=m)             return 0;         if(mat[i][j]==0)             return 0;         if(dp[i][j]!=-1)             return dp[i][j];