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!

Group Anagrams

Problem Statement: Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

Source: https://leetcode.com/problems/group-anagrams/

Leetcode Difficulty: Medium

Asked in: Facebook Amazon ,Apple  Netflix Google

Code:

    def groupanagrams(self, strs):
        """
        strs: List[str]
        return: List[List[str]]
        """
        if len(strs)==0: return [[""]]
        elif len(strs)==1: return [[strs[0]]]
        
        ans = collections.defaultdict(list)
        for s in strs:
            ans[tuple(sorted(s))].append(s)
        return ans.values()

Thought Process / Explanation:

The keyword "grouping" hints me to use a dictionary where key will be a common representation of strings and value be their original form. Also, we know that sorted anagrams represent the exact same string.

Thank You!

Contains Duplicate II

Problem Statement: Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

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

Example 2:

Input: nums = [1,0,0,1,1], k = 1
Output: true

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

Source: https://leetcode.com/problems/contains-duplicate-ii/

Leetcode Difficulty: Easy

Asked in: Google

Code:

    def duplicate_ii(self, nums, k):
        """
        :nums: List[int]
        :k: int
        :return: bool
        """
        big_idx_map={}
        
        for idx, i in enumerate(nums):
            if i not in big_idx_map:
                big_idx_map[i] = idx
            else:
                if (idx-big_idx_map[i])<=k:
                    return True
                else:
                    big_idx_map[i]=idx
        return False

Thought Process / Explanation:

We are given k (difference to compare against) and the value at any two different idx can be atmost k. Since we will need to find all positions of every element, this hints me to use a dictionary that would help me store numbers and lists idx as key-value pair. Finally, I can iterate through the idx list and get pair that satisfies the condition of <=k. 

But can we do better and reduce this idx list traversal?

One thing to notice over here is that the difference between nearby values will always be less than the difference between farther apart ones. And since we need to satisfy the at-most condition, So, instead of storing list of idx as a value in our dictionary, we can only get done by storing the next higher idx of the occurrence of a particular number and do the comparison with that. That's what is written in the code above.

Thank You!