LeetCode 519: Random Flip Matrix Solution

Master LeetCode problem 519 (Random Flip Matrix), a medium 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.

519. Random Flip Matrix

Medium

Hash Table Math Reservoir Sampling Randomized

Problem Explanation

Explanation

To solve this problem efficiently, we can use a combination of techniques. We can map the 2D grid to a 1D array to optimize memory usage. Then, we can use a map or a set to keep track of the available indices that can be flipped. When flipping an index, we need to ensure that it is removed from the available indices set and update the mapping accordingly. Resetting the matrix simply involves clearing the set of available indices.

The time complexity for each flip operation is O(1), as we are choosing an available index randomly. The space complexity is O(m*n) for storing the matrix and O(k) for storing the set of available indices, where k is the number of available indices.

Solution Code

import java.util.*;

class Solution {
    private int rows, cols, total;
    private Random rand;
    private Map<Integer, Integer> map;

    public Solution(int m, int n) {
        rows = m;
        cols = n;
        total = m * n;
        rand = new Random();
        map = new HashMap<>();
    }

    public int[] flip() {
        int r = rand.nextInt(total--);
        int x = map.getOrDefault(r, r);
        map.put(r, map.getOrDefault(total, total));
        return new int[]{x / cols, x % cols};
    }

    public void reset() {
        map.clear();
        total = rows * cols;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 519 (Random Flip Matrix)?

This page provides optimized solutions for LeetCode problem 519 (Random Flip 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 519 (Random Flip Matrix)?

The time complexity for LeetCode 519 (Random Flip Matrix) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 519 on DevExCode?

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

Back to LeetCode Solutions