LEETCODE SOLUTIONS

Edit Distance Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: 1. Insert a character 2. Delete a character 3. Replace a character Example 1: Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e') Example 2: Input: word1 = "intention", word2 = "execution" Output: 5 Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u') Solution in Java : class Solution {     public int minDistance(String word1, String word2) {         int m = word1....

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

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

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

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

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

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

17. Find All Anagrams in the String Given a string  s  and a  non-empty  string  p , find all the start indices of  p 's anagrams in  s . Strings consists of lowercase English letters only and the length of both strings  s  and  p  will not be larger than 20,100. The order of output does not matter. Example 1: Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc". Example 2: Input: s: "abab" p: "ab" Output: [0, 1, 2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab". Solution in ...

16. Odd Even Linked List Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. Example 1: Input: 1->2->3->4->5->NULL Output: 1->3->5->2->4->NULL Example 2: Input: 2 ->1->3->5->6->4->7->NULL Output: 2->3->6->7->1->5->4->NULL Note: The relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on ... Solution in Java : class Solution  { public ListNode oddEvenList(ListNode head) {     if(head == null)          return head;     ListNode result = head;     ListNode p1 = head;   ...

15. Maximum Sum Circular Subarray Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C. Here, a circular array means the end of the array connects to the beginning of the array.   (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.) Also, a subarray may only include each element of the fixed buffer A at most once.   (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.) Example 1: Input: [1,-2,3,-2] Output: 3 Explanation: Subarray [3] has maximum sum 3 Example 2: Input: [5,-3,5] Output: 10 Explanation:   Subarray [5,5] has maximum sum 5 + 5 = 10 Example 3: Input: [3,-1,2,-1] Output: 4 Explanation:   Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4 Example 4: Input: [3,-2,2,-3] Output: 3 Explanation:   Subarray [...