The O(n) Club: Largest Divisible Subset: DP, Java, and Chaos Prevention

The O(n) Club: Largest Divisible Subset—DP, Java, and Chaos Prevention

⚡ TL;DR

This problem is basically “who can divide whom at the nerd party?” Brute force tries every group, melts your CPU. Smart way: sort, DP, backtrack—go home early.

// Brute force (just kidding, don’t use)
public List<Integer> largestDivisibleSubset(int[] nums) {
    // O(2^n) : You’ll finish when AI rules the earth
    return new ArrayList<>();
}

🧠 How Devs Usually Mess This Up

If you think brute force will impress the interviewer, prepare for disappointment. Most folks also forget divisibility has trust issues—it isn’t just about neighbors. Got no sort? Watch all those delicious divisibility chains slip through your fingers like wet spaghetti.

🔍 What’s Actually Going On

Imagine a “sensible conga line”: every bigger number can only join if it’s a perfect multiple of someone ahead. Sort the numbers, then for each dancer, look back for the best chain they could join. If a higher number is divisible by a lower, it can piggyback on their subset length.

This isn’t brute force, it’s dynamic programming—think advance reservations at the subset hotel. And yeah, backtracking is basically your checkout receipt.

🛠️ PseudoCode

• Sort the array nums ascending
• For every i in nums:
  • Look at every j < i
  • If nums[i] % nums[j] == 0 and chaining j beats current, update subset length and predecessor
• Track longest chain and its endpoint
• Backtrack via predecessors to build your subset

// Java Pseudo-setup
Arrays.sort(nums);
int[] dp = new int[nums.length]; // Big chain ending here
int[] prev = new int[nums.length]; // Last guy in chain
// Fill dp and prev by the rules
// Rewind for answer

💻 The Code

public List<Integer> largestDivisibleSubset(int[] nums) {
    if (nums == null || nums.length == 0) return new ArrayList<>();
    int n = nums.length;
    Arrays.sort(nums);
    int[] dp = new int[n];
    int[] prev = new int[n];
    Arrays.fill(dp, 1);
    Arrays.fill(prev, -1);
    int maxIndex = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > dp[maxIndex]) {
            maxIndex = i;
        }
    }
    List<Integer> res = new ArrayList<>();
    for (int k = maxIndex; k >= 0; k = prev[k]) {
        res.add(nums[k]);
        if (prev[k] == -1) break;
    }
    Collections.reverse(res);
    return res;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Zeroes: Outlawed. Division by zero is the dark web of math.
• Duplicate numbers? No drama, but the problem usually calls for unique numbers—read the fine print.
• Forgetting to sort: Like cooking before you buy groceries. Leads to chaos.
• Complexity: Time is O(N²) (still way less than O(2^N) sadness). Space O(N) for chains and backtracking. Roomy enough for big party arrays.

🧠 Interviewer Brain-Tattoo

Remember: “Dynamic Programming is just Brute Force that went to therapy.”