832. Flipping an Image

Approach 1: Using map

def flipAndInvertImage(self, A):
"""
:type A: List[List[int]]
:rtype: List[List[int]]
"""
def invert(i):
return 0 if i == 1 else 1
def flip(l):
return list(map(invert, l))[::-1]
return map(flip, A)

This approach is not the best since we're iterating over each element in each row of the input list, and is among the bottom 1% of all leetcode submissions

Time Complexity: O(N), where N is the total number of pixels

Space Complexity: O(1)

Approach 2: Using lambda instead of the map

def flipAndInvertImage(self, A):
"""
:type A: List[List[int]]
:rtype: List[List[int]]
"""
def flip(l):
return list(map(lambda i: 0 if i == 1 else 1, l))[::-1]
return map(flip, A)

This method has improved performance but there is still scope for improvement for the invert function. This solution comes up to 26% percentile on leetcode

Time Complexity: O(N), where N is the total number of pixels

Space Complexity: O(1)

Approach 3: Improved invert

def flipAndInvertImage(self, A):
"""
:type A: List[List[int]]
:rtype: List[List[int]]
"""
def flip(l):
return list(map(lambda i: 1-i, l))[::-1]
return map(flip, A)

This solution comes up to a solid 88% percentile, and the only difference between this and the solution at 100% is that the 100% solution avoid using 2 maps

Time Complexity: O(N), where N is the total number of pixels

Space Complexity: O(1)

As you can see that the performance improves regardless of the time complexity because of the additional overhead of the functions on the algorithm regardless of the time complexity, especially since the input size is so relatively small