Leetcode!
  • LeetCode!
  • My personal guide to Leetcode
  • Array
    • 11. Container With Most Water
    • 15. 3Sum
    • 219. Contains Duplicate II
    • 238. Product of Array Except Self
    • 245. Shortest Word Distance III
    • 392. Is Subsequence
    • 442. Find All Duplicates in an Array
    • 561. Array Partition I
    • 661. Image Smoother
    • 697. Degree of an Array
    • 723. Candy Crush
    • 832. Flipping an Image
  • Backtracking
    • 294. Flip Game II
    • 401. Binary Watch
    • 1079. Letter Tile Possibilities
  • Binary Search
    • 744. Find Smallest Letter Greater Than Target
    • 852. Peak Index in a Mountain Array
  • String
    • 6. ZigZag Conversion
    • 17. Letter Combinations of a Phone Number
    • 38. Count and Say
    • 521. Longest Uncommon Subsequence I
    • 544. Output Contest Matches
    • 937. Reorder Data in Log Files
  • Design
    • 251. Flatten 2D Vector
    • 281. Zigzag Iterator
  • Hash Table
    • 1. Two Sum
    • 508. Most Frequent Subtree Sum
    • 884. Uncommon Words from Two Sentences
    • 734. Sentence Similarity
  • Linked List
    • 2. Add Two Numbers
  • Unsorted
    • 917. Reverse Only Letters
  • Math
    • 43. Multiply Strings
    • 462. Minimum Moves to Equal Array Elements II
    • 553. Optimal Division
    • 800. Similar RGB Color
  • Greedy
    • 406. Queue Reconstruction by Height
    • 861. Score After Flipping Matrix
  • Tree
    • 701. Insert into a Binary Search Tree
    • 897. Increasing Order Search Tree
  • Divide and Conquer
    • 53. Maximum Subarray
  • Dynamic Programming
    • 62. Unique Paths
    • 63. Unique Paths II
    • 64. Minimum Path Sum
    • 120. Triangle
    • 198. House Robber
    • 213. House Robber II
    • 303. Range Sum Query - Immutable
    • 518. Coin Change 2
    • 750. Number Of Corner Rectangles
    • 337. House Robber III
  • Depth first search
    • 841. Keys and Rooms
  • Trie
    • 677. Map Sum Pairs
  • Two pointer
    • 42. Trapping Rain Water
Powered by GitBook
On this page
  • Approach 1: Brute Force
  • Approach 2: Greedy Solution
  1. Greedy

861. Score After Flipping Matrix

Approach 1: Brute Force

One thing note was that trying all combinations was crazy stupid, since it is a runtime of 2^(M*N) so there was a way that we had to optimize

Approach 2: Greedy Solution

class Solution(object):
    def matrixScore(self, A):
        """
        https://leetcode.com/problems/score-after-flipping-matrix/description/
        :type A: List[List[int]]
        :rtype: int
        """
        R, C = len(A), len(A[0])
        ans = 0
        for c in range(C):
            col = 0
            for r in range(R):
                col += A[r][c] ^ A[r][0]
            ans += max(col, R - col) * (1 << (C - 1 - c))
        return ans

This one took a while. Making the most significant bit one will give the highest return since if those are one then we can get a sum of at least R * 2^(C-1). Once we have decided to toggle all of those to be one, we have to iterate through all of the other columns to decide which ones to toggle based on the number of ones that they have, and toggle only if they have less ones than zeroes

An optimized way to do this would be XOR all the columns with the first column and decide which ones to toggle based on their counts of ones.

Calculating the end sum can be optimized even further by using bit shifting since we have to calculate a power of 2

Time Complexity: O(R*C) where R and C are the dimensions of the matrix

Space Complexity: O(1)

Previous406. Queue Reconstruction by HeightNext701. Insert into a Binary Search Tree

Last updated 6 years ago