We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count the Number of K-Free Subsets

Number: 2738

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given an array of distinct integers and an integer k, count how many subsets of the array (including the empty set) do not contain any two numbers with an absolute difference equal to k. Such subsets are called k–Free subsets.

Key Insights

  • Two numbers x and y conflict if |x - y| equals k.
  • Because conflicts only occur between numbers differing exactly by k, any conflict graph forms disjoint chains (or isolated nodes).
  • For any chain (i.e. an arithmetic progression having consecutive differences equal to k), the allowed selections are equivalent to choosing an independent set in a line graph.
  • The number of independent sets in a chain of length L can be computed with a simple Fibonacci-style recurrence: dp[i] = dp[i – 1] + dp[i – 2].
  • Since there is no conflict between numbers in different connected components, the overall count is the product of counts for each component.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the input array (plus a small extra factor for processing each connected component which is bounded by n). Space Complexity: O(n), for storing the set of numbers and the visited markers during the DFS.

Solution

We solve the problem by first recognizing that a conflict only exists between a number x and another number x+k (or x-k). Therefore, build a graph with nodes as the given numbers and an edge between x and x+k (if both exist). This graph is a collection of disjoint chains (or isolated nodes).

For each connected component:

  1. Perform a DFS to retrieve all nodes in the component.
  2. Sort the component. (Due to the nature of the edge, nodes in a component will form an arithmetic progression with difference k.)
  3. Compute the number of valid independent sets using dynamic programming. For a chain of length L, the recurrence is:
    • dp[0] = 1 (base case for empty prefix)
    • dp[1] = 2 (pick the single node or not)
    • dp[i] = dp[i - 1] + dp[i - 2]

Since components are independent, multiply the counts for all components to get the final result.

Code Solutions

# Python solution with line-by-line comments

def countKFreeSubsets(nums, k):
    # Use a set for quick membership tests.
    numSet = set(nums)
    # Visited set to keep track of already processed nodes
    visited = set()
    
    # Function to perform DFS and return the connected component (chain) as a list.
    def dfs(x, component):
        visited.add(x)
        component.append(x)
        # Check neighbor: x+k
        if x + k in numSet and (x + k) not in visited:
            dfs(x + k, component)
        # Check neighbor: x-k
        if x - k in numSet and (x - k) not in visited:
            dfs(x - k, component)
    
    # List to hold count values for each connected component.
    components_counts = []
    
    # Iterate through all numbers to gather connected components using DFS.
    for num in nums:
        if num not in visited:
            component = []
            dfs(num, component)
            # sort the component; due to the graph construction,
            # if proper chaining exists, sorting gives an arithmetic progression with difference k.
            component.sort()
            L = len(component)
            # Compute number of independent sets in a chain of length L.
            # Handle chain length using DP.
            if L == 0:
                ways = 1
            elif L == 1:
                ways = 2  # either take the number or not
            else:
                dp0, dp1 = 1, 2
                for i in range(2, L+1):
                    dp0, dp1 = dp1, dp0 + dp1
                ways = dp1
            components_counts.append(ways)
    
    # Multiply the counts from all connected components.
    result = 1
    for count in components_counts:
        result *= count
    return result

# Example usage:
print(countKFreeSubsets([5,4,6], 1))   # Expected output: 5
print(countKFreeSubsets([2,3,5,8], 5))   # Expected output: 12
print(countKFreeSubsets([10,5,9,11], 20))# Expected output: 16
← Back to All Questions