move O(MN) to sol1
add sol with O(1) space complexity