Longest Sublist with K Distinct Numbers

February 24, 2021


Given an integer k and a list of integers nums, return the length of the longest sublist that contains at most k distinct integers. Problem link:


Python Two-Pointer/Sliding-Window and Dictionary approach

Use 2 pointers l(left) and r(right) to traverse the array


We use a dictionary curr_set to keep track of elements in the current window. When we find an element not in the current set we start popping elements from the left


class Solution:
    def solve(self, k, nums):
        if k == 0:
            return 0
        if not nums:
            return 0
        curr_set = collections.defaultdict(int)
        l = 0
        max_len = 0
        curr_len = 0

        for r in range(0, len(nums)):
            while len(curr_set) >= k and nums[r] not in curr_set:
                curr_set[nums[l]] -= 1
                if curr_set[nums[l]] == 0:
                    del curr_set[nums[l]]
                l += 1
            curr_set[nums[r]] += 1
            max_len = max(max_len, r - l + 1)
        return max_len

Time complexity


Space complexity

O(k) where k is the size of curr_set

Written by Ganesh Iyer A software engineer building platforms for leveraging artificial intelligence in healthcare. Follow me on twitter