LeetCode 2732: Find a Good Subset of the Matrix Solution

Master LeetCode problem 2732 (Find a Good Subset of the Matrix), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2732. Find a Good Subset of the Matrix

Hard

Array Hash Table Bit Manipulation Matrix

Problem Explanation

Explanation:

To solve this problem, we can iterate through all possible subsets of rows and check if the sum of each column in that subset satisfies the given condition. We can use backtracking to generate all subsets efficiently and keep track of the best subset found so far.

Start by defining a helper function that checks if a subset of rows satisfies the condition.
Use backtracking to generate all possible subsets of rows.
For each subset generated, check if it satisfies the condition.
Keep track of the best subset found so far.
Return the row indices of the best subset as the result.

Time Complexity: The time complexity of this approach is O(2^m * n), where m is the number of rows and n is the number of columns. This is because we are generating all possible subsets of rows.

Space Complexity: The space complexity is O(m) to store the current subset being processed.

Solution Code

class Solution {
    private int[] result;
    
    public int[] findGoodSubset(int[][] grid) {
        result = new int[grid.length];
        backtrack(grid, 0, new ArrayList<>());
        return Arrays.copyOf(result, Arrays.stream(result).filter(val -> val != -1).count());
    }
    
    private void backtrack(int[][] grid, int row, List<Integer> subset) {
        if (row >= grid.length) {
            if (isValidSubset(grid, subset) && subset.size() > Arrays.stream(result).filter(val -> val != -1).count()) {
                result = new int[grid.length];
                for (int i = 0; i < subset.size(); i++) {
                    result[i] = subset.get(i);
                }
            }
            return;
        }
        
        subset.add(row);
        backtrack(grid, row + 1, subset);
        subset.remove(subset.size() - 1);
        backtrack(grid, row + 1, subset);
    }
    
    private boolean isValidSubset(int[][] grid, List<Integer> subset) {
        int cols = grid[0].length;
        int[] colSums = new int[cols];
        for (int row : subset) {
            for (int j = 0; j < cols; j++) {
                colSums[j] += grid[row][j];
            }
        }
        int subsetLen = subset.size();
        for (int sum : colSums) {
            if (sum > Math.floor(subsetLen / 2.0)) {
                return false;
            }
        }
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2732 (Find a Good Subset of the Matrix)?

This page provides optimized solutions for LeetCode problem 2732 (Find a Good Subset of the Matrix) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2732 (Find a Good Subset of the Matrix)?

The time complexity for LeetCode 2732 (Find a Good Subset of the Matrix) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2732 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2732 in Java, C++, or Python.

Back to LeetCode Solutions