Remove Duplicates from Sorted List II

Problem Statement: Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

Source: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

Leetcode Difficulty: Medium

Code:

    def deleteDuplicates(self, head):
        """
        head: ListNode
        return: ListNode
        """
        
        curr=head
        tmp=ListNode(-1, head)
        prev=tmp
        
        while curr:
            
            if curr.next and curr.val==curr.next.val:              
                while curr.next and curr.val==curr.next.val:
                    curr=curr.next
                prev.next=curr.next
            else:
                prev = prev.next
            
            curr=curr.next
            
        return tmp.next

Thought Process / Explanation:

It's all about adjusting pointers by making the adjacent comparisons. Need to take care of one special case, when all elements are the same. We define a dummy node for that and do a final return as per that.

Thank You!

Remove Nth Node From End of List

Problem Statement: Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Source: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Asked in: Facebook Amazon ,Apple  Netflix Google

Leetcode Difficulty: Medium

Code:

    def removeNthFromEnd(self, head, n):
        """
        head: ListNode
        n: int
        return: ListNode
        """
        fastptr=head
        slowptr=head
        prev=None
        count=1
        
        while count!=n:
            fastptr=fastptr.next
            count+=1
        
        while fastptr.next:
            fastptr=fastptr.next
            prev=slowptr
            slowptr=slowptr.next
            
        
        if prev:
            prev.next=slowptr.next
        else:
            head = slowptr.next
        return head

Thought Process / Explanation:

You can always find the length first and then iterate (L-n) positions from start. But that would require you to do 2 passes on the entire list. So for a single pass, clearly, we need to maintain 2 ptrs (Fast and Slow pointers are very useful in solving LL questions) One starts at the nth position from start and another from Zeroth. By the time ahead one reaches NULL, the previous one will reach the nth position from the end.

Thank You!

Find Largest Value in Each Tree Row

Problem Statement: Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Example 1:

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

Constraints:

• The number of nodes in the tree will be in the range [0, 104].
• -231 <= Node.val <= 231 - 1

Source: https://leetcode.com/problems/find-largest-value-in-each-tree-row/

Asked in: Facebook Amazon ,Apple

Leetcode Difficulty: Medium

Code:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
class Solution(object):
    
    def find_largest_in_each_row(self, root, level=0, traversed={}):
        
        if not root: return {}
        
        if level in traversed:
            traversed[level]=max(traversed[level], root.val)
        else:
            traversed[level]=root.val
            
        self.find_largest_in_each_row(root.left, level+1, traversed)
        self.find_largest_in_each_row(root.right, level+1, traversed)
        return traversed
    
    def largestValues(self, root):
        """
        root: TreeNode
        return: List[int]
        """
        traversed={}
        return [v for k,v in self.find_largest_in_each_row(root, 0, traversed).items()]

Thought Process / Explanation:

Since we need to print the largest element at every level, we will have to keep track of the level of each node and some kind of counter to store max per level. The information of level can be added in the recursion call itself..and for the counter, we can have an (int, int) dict to store level and max value found till a point for that level.

Thank You!

Symmetric Tree

Problem Statement: Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

Source: https://leetcode.com/problems/symmetric-tree/

Asked in: Facebook Amazon ,Apple

Leetcode Difficulty: Easy

Code:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):    
    def check(self, root1, root2):
        if root1==None and root2==None: return True
        elif root1==None and root2!=None: return False
        elif root1!=None and root2==None: return False
        
        if root1.val==root2.val:
            if self.check(root1.left, root2.right) and self.check(root1.right, root2.left):
                return True
            else:
                return False
        else:
            return False
    
    def isSymmetric(self, root):
        return self.check(root, root)

Thought Process / Explanation:

This problem also follows a typical pattern like other tree problems... we check for the root node and recursively call for left and right parts of the tree. Here, since we spawn two trees,  so the left side of one should be same as the right side of one and vice-versa.

Thank You!

Path Sum

Problem Statement: Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

Source: https://leetcode.com/problems/path-sum/

Asked in: Facebook Amazon ,Apple

Leetcode Difficulty: Easy

Code:

    def check(self, root, targetSum, pathSum=0):
        if not root: return
            
        pathSum+=root.val
        
        if pathSum==targetSum and root.left==None and root.right==None: return True
        return self.check(root.left, targetSum, pathSum) or self.check(root.right, targetSum, pathSum)
    
    def haspathsum(self, root, targetSum):
        """
        root: TreeNode
        targetSum: int
        return: bool
        """
        return self.check(root, targetSum)

Thought Process / Explanation:

Keep summing the root values in paths we iterate and compare pathSum with targetSum if the root at that point is a leaf node. Do this for left and right parts of the tree.

Thank You!

Most Frequent Subtree Sum

Problem Statement: Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.

The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

Example 1:

Input: root = [5,2,-3]
Output: [2,-3,4]

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105

Source: https://leetcode.com/problems/most-frequent-subtree-sum/

Leetcode Difficulty: Medium

Code:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    
    def __init__(self):
        self.subtree_sums = {}
        self.max_freq=-1
        
    def get_max_subtree_sum(self, root):
        if root==None: 
            return 0
        
        leftsum = self.get_max_subtree_sum(root.left)
        rightsum = self.get_max_subtree_sum(root.right)
        currval = root.val
        
        summation = currval + rightsum + leftsum
        self.subtree_sums[summation] = self.subtree_sums.get(summation, 0)+1
        self.max_freq = max(self.max_freq, self.subtree_sums[summation])
        return summation
        
    def findFrequentTreeSum(self, root):
        self.get_max_subtree_sum(root)
        result=[]
        for k,v in self.subtree_sums.items():
            if v==self.max_freq:
                result.append(k)
        return result

Thought Process / Explanation:

We know that sum of the subtree rooted at a certain node is left sum + right sum + curr val. We need to store the sum with it's count and later return only max frequency sum -- for this keeping a dictionary sounds good and also maintaining global max_freq counter for comparison.

Thank You!

Top K Frequent Words

Problem Statement: Given an array of strings words and an integer k, return the k most frequent strings. Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1:

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

Constraints:

• 1 <= words.length <= 500
• 1 <= words[i] <= 10
• words[i] consists of lowercase English letters.
• k is in the range [1, The number of unique words[i]]

Source: https://leetcode.com/problems/top-k-frequent-words/

Leetcode Difficulty: Medium

Asked in: Facebook Amazon ,Apple  Netflix Google

Code:

    def topKfrequent(self, words, k):
        """
        words: List[str]
        k: int
        return: List[str]
        """
        counter={}
        for i in words:
            if i in counter:
                counter[i]+=1
            else:
                counter[i]=1
    
        heap=[]
        for key,value in counter.items():
            heapq.heappush(heap, (-1*value, key))
    
        return [heapq.heappop(heap)[1] for word in range(k)]

Thought Process / Explanation:

Heapq uses a priority queue to implement heaps. So by default, we will get lexicographically sorted strings. Now the task is to main freq and word pair in a heap where the top is max-freq.

Thank You!

K Closest Points to Origin

Problem Statement: Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

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

Constraints:

• 1 <= k <= points.length <= 104
• -104 < xi, yi < 104

Source: https://leetcode.com/problems/k-closest-points-to-origin/

Leetcode Difficulty: Medium

Code:

    def get_distance(self, point):
        origin=[0,0]
        return ((point[1]-origin[1])**2 + (point[0]-origin[0])**2)**0.5
    
    def kclosest(self, points, k):
        """
        points: List[List[int]]
        k: int
        return: List[List[int]]
        """
        
        heap=[]
        for point in points[:k]:
            distance = self.get_distance(point)
            heapq.heappush(heap, (-1*distance,point))
        
        for point in points[k:]:
            distance = -1*self.get_distance(point)
            
            top = heapq.heappop(heap)
            
            if top[0]<distance:
                heapq.heappush(heap, (distance,point))
            else:
                heapq.heappush(heap, top)
        
        return [heapq.heappop(heap)[1] for _ in range(k)]

Thought Process / Explanation:

The keyword "k closest" hints me to give a shot to heaps. Since heapq implements min-heap by default. We multiply the distance by -1 to make sure the absolute largest is on top every time (acting as max-heap). The rest is just a comparison from the top and updating things.

Thank You!

Top K Frequent Elements

Problem Statement: 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 <= 105
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Source: https://leetcode.com/problems/top-k-frequent-elements/

Leetcode Difficulty: Medium

Asked in: Amazon

Code:

    def topKfrequent(self, nums, k):
        """
        nums: List[int]
        k: int
        return: List[int]
        """
        counter={}
        for i in nums:
            if i in counter:
                counter[i]+=1
            else:
                counter[i]=1
        
        heap=[]
        for idx, (key,value) in enumerate(counter.items()):
            if idx<k:
                heapq.heappush(heap,(value,key))
            else:
                top=heapq.heappop(heap)
                if top[0]<value:
                    heapq.heappush(heap,(value,key))
                else:
                    heapq.heappush(heap,top)
           
        return [heapq.heappop(heap)[1] for _ in range(k)]

Thought Process / Explanation:

The keyword "k frequent" hints me to give a shot to heaps. Heap of size K is enough as we will need to return atmost k elements. Since we need to return k frequent, we can create a min-heap with (value,key) pair and later compare it with the value on the pop operation. Finally, return the key corresponding to each value in min-heap.

Thank You!

Kth Largest Element in an Array

 Problem Statement: Given an integer array nums and an integer k, return the  kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

• 1 <= k <= nums.length <= 104
• -104 <= nums[i] <= 104

Source: https://leetcode.com/problems/kth-largest-element-in-an-array/

Leetcode Difficulty: Medium

Asked in: Facebook Amazon ,Apple  Netflix Google

Code:

import heapq

def findKthlargest(self, nums, k):
        """
        nums: List[int]
        k: int
        return: int
        """
        
        heap=[]
        
        for i in nums[:k]:
            heapq.heappush(heap, i)
        
        for i in nums[k:]:
            top = heapq.heappop(heap)
            if i>top:
                heapq.heappush(heap, i)
            else:
                heapq.heappush(heap, top)
        
        
        return heapq.heappop(heap)

Thought Process / Explanation:

The keyword "kth largest" hints me to give a shot to heaps. Heap of size K is enough as we will need to return atmost k elements even if the problem is extended. Min heap suits here because we can replace the top if it's shorter than the new element to be examined.

Thank You!

Subarray Sum Equals K

Problem Statement: Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

Source: https://leetcode.com/problems/subarray-sum-equals-k/

Leetcode Difficulty: Medium

Asked in: Facebook Amazon   Netflix Google

Code:

    def subarraysum(self, nums, k):
        """
        nums: List[int]
        k: int
        return: int
        """
        
        prefix_cnt={0:1}
        summ=0
        result=0
        
        for i in nums:
            summ+=i
            
            if summ-k in prefix_cnt:
                result+=prefix_cnt[summ-k]
            
            if summ in prefix_cnt:
                prefix_cnt[summ]+=1
            else:
                prefix_cnt[summ]=1
            
        return result 

Thought Process / Explanation:

Hints to use prefix sum because of finding subarray of sum k. Because if Prefix[i]-Prefix[j] == 0 then i+1 to j in original array sums to ZERO. Here instead of 0, we have been given K. And overall since we need to return the count of such subarrays.. so probably using some dict.

Thank You!

Maximum Subarray

 Problem Statement: Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. A subarray is a contiguous part of an array

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Source: https://leetcode.com/problems/maximum-subarray/

Leetcode Difficulty: Easy

Asked in: Amazon ,

Code:

    def maxsubarray(self, nums: List[int]) -> int:
        curr_sum=nums[0]
        final_sum=curr_sum
        for i in nums[1:]:
            if curr_sum<0: curr_sum=0
            curr_sum += i
            final_sum = max(curr_sum, final_sum)
        return final_sum

Thought Process / Explanation:

It's a pretty standard problem that uses Kadane's Algorithm.

Thank You!