Kth Distinct String in an Array

main.md

Kth Distinct String in an Array

Question on Leetcode - Easy

Approach

The appraoch used is to creates two sets, distincts and seen. The distincts set will store the unique elements of the input array arr, and the seen set will store the elements that have already been seen.

We then iterate through the input array arr. For each element num, the code checks if num is in the seen set. If it is, then the code removes num from the distincts set. Otherwise, the code adds num to both the distincts and seen sets.

After the loop has finished, the code checks if the length of the distincts set is less than the input k. If it is, then the code returns the empty string. Otherwise, the code returns the k-th element of the distincts set.

Code

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        distincts, seen = set(), set()
        for num in arr:
            if num in seen:
                distincts.discard(num)
            else:
                distincts.add(num)
            seen.add(num)
        if len(distincts) < k:
            return ""
        return [i for i in arr if i in distincts][k-1]

Complexities

• Time Complexity: O(n)
• Space Complexity: O(n)