LEETCODE SOLUTIONS

371 .  Sum of Two Integers   Given two integers  a  and  b , return  the sum of the two integers without using the operators   +   and   - .   Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5   Constraints: -1000 <= a, b <= 1000 Solution :  C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java :  class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :

Top K Frequent Elements Given an integer array  nums  and an integer  k , return  the   k   most frequent elements . You may return the answer in  any order .   Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1]   Constraints: 1 <= nums.length <= 10 5 -10 4  <= nums[i] <= 10 4 k  is in the range  [1, the number of unique elements in the array] . It is  guaranteed  that the answer is  unique .   Follow up:  Your algorithm's time complexity must be better than  O(n log n) , where n is the array's size. Solution : class Solution:     def topKFrequent(self, n: List[int], k: int) -> List[int]:                  # [1,1,1,2,2,3] &  k = 2                  f = [[] for i in range(len(n) + 1)]         # f = [...

Given an integer  n , return  an array  ans  of length  n + 1  such that for each  i   ( 0 <= i <= n ) ,  ans[i]  is the  number of  1 's  in the binary representation of  i .   Example 1: Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10 Example 2: Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101   Constraints: 0 <= n <= 10 5   Follow up: It is very easy to come up with a solution with a runtime of  O(n log n) . Can you do it in linear time  O(n)  and possibly in a single pass? Can you do it without using any built-in function (i.e., like  __builtin_popcount  in C++)?   Solution : class Solution:     def countBits(self, n: int) -> List[int]:         dp = [0] * (n+1)         c = 1        ...

66.  Number of Connected Components in an Undirected Graph Question Link :  check here Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Example 1:      0          3      |          |      1 --- 2    4 Givenn = 5andedges = [[0, 1], [1, 2], [3, 4]], return2. Example 2:      0           4      |           |      1 --- 2 --- 3 Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [3, 4]], return1. Note: You can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges. Solution : class Solution: def counComponents(self, n: int, edges : List[List[int]]) -> i...

322 .  Coin Change 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.   Example 1: Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = [2], amount = 3 Output: -1 Example 3: Input: coins = [1], amount = 0 Output: 0   Constraints: 1 <= coins.length <= 12 1 <= coins[i] <= 2 31  - 1 0 <= amount <= 10 4   Solution : class Solution:     def coinChange(self, coins: List[int], amount: int) -> int:         dp = [amount + 1] * (amount + 1) #[0...7]         dp[0] = 0        ...

300 .  Longest Increasing Subsequence Given an integer array  nums , return the length of the longest strictly increasing subsequence. A  subsequence  is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example,  [3,6,2,7]  is a subsequence of the array  [0,3,1,6,2,2,7] .   Example 1: Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. Example 2: Input: nums = [0,1,0,3,2,3] Output: 4 Example 3: Input: nums = [7,7,7,7,7,7,7] Output: 1   Constraints: 1 <= nums.length <= 2500 -10 4  <= nums[i] <= 10 4   Solution : class Solution:     def lengthOfLIS(self, n: List[int]) -> int:         lis = [1] * len(n)         for i in range(len(n)-1, -1, -1):             for j in ra...

  295 .  Find Median from Data Stream The  median  is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values. For example, for  arr = [2,3,4] , the median is  3 . For example, for  arr = [2,3] , the median is  (2 + 3) / 2 = 2.5 . Implement the MedianFinder class: MedianFinder()  initializes the  MedianFinder  object. void addNum(int num)  adds the integer  num  from the data stream to the data structure. double findMedian()  returns the median of all elements so far. Answers within  10 -5  of the actual answer will be accepted.   Example 1: Input ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Output [null, null, null, 1.5, null, 2.0] Explanation MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFin...