Swift
Intuition\nThe problem is asking to randomly pick an index (i, j) where matrix[i][j] == 0 and flips it to 1. All the indices (i, j) where matrix[i][j] == 0 shou
# Intuition\nThe problem is asking to randomly pick an index (i, j) where matrix[i][j] == 0 and flips it to 1. All the indices (i, j) where matrix[i][j] == 0 should be equally likely to be returned. The challenge here is to optimize the algorithm to minimize the number of calls made to the built-in random function of your language and optimize the time and space complexity.\n\n# Approach\nThe approach used here is to maintain a mapping of the indices of the zeros in the matrix. We start by initializing a total variable to m*n (the total number of zeros in the matrix) and a map to store the indices of the flipped cells.\n\nIn the flip function, we generate a random number between 0 and total-1, and then swap the value at the random index with the value at the last index in the map. This ensures that all the indices where matrix[i][j] == 0 are equally likely to be returned. We then decrement the total by 1 to reflect the fact that one zero has been flipped to 1.\n\nThe reset function simply resets the map and total to their initial states, effectively setting all the values in the matrix back to 0.\n\n\n# Complexity\n- Time complexity: The time complexity for both the flip and reset functions is O(1), as they both perform a constant amount of work regardless of the size of the matrix.\n\n\n- Space complexity: The space complexity is O(m\u2217n), where m and n are the dimensions of the matrix. This is because we need to store the indices of the zeros in the matrix in the map. In the worst case, all the cells in the matrix are zeros, so we need to store m*n indices. However, this space complexity is optimal for this problem, as we need to keep track of the positions of all the zeros in the matrix.\n\n# Code\n```\nimport Foundation\n\nclass Solution {\n    var total: Int\n    var map: [Int: Int]\n    var m: Int\n    var n: Int\n\n    init(_ m: Int, _ n: Int) {\n        self.m = m\n        self.n = n\n        self.total = m * n\n        self.map = [Int: Int]()\n    }\n    \n    func flip() -> [Int] {\n        let rand = Int.random(in: 0..<total)\n        let x = map[rand] ?? rand\n        let y = map[total-1] ?? (total-1)\n        \n        map[rand] = y\n        map[total-1] = x\n        total -= 1\n        \n        return [x / n, x % n]\n    }\n    \n    func reset() {\n        map.removeAll()\n        total = m * n\n    }\n}\n\n/**\n * Your Solution object will be instantiated and called as such:\n * let obj = Solution(m, n)\n * let ret_1: [Int] = obj.flip()\n * obj.reset()\n */\n\n```
['Swift']