Find if Array Can Be Sorted - Leetcode 3011 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
5:03 - Coding Explanation
7:10 - Drawing Explanation
11:56 - Coding Explanation

leetcode 3011

#neetcode #leetcode #python

[michaelmcmanus]

was just looking at this problem and didn't expect there to be a neetcode video for it! always a treat

[caresword]

i finnaly did a leetcode problem all by-myself!

this was my code.

class Solution(object):
def canSortArray(self, nums):
for i in range(len(nums)-1):
for i in range(len(nums)-1):
j = i+1
if bin(nums[i]).count("1") == bin(nums[j]).count("1") and nums[i] > nums [j]:
temp = nums[i]

nums[i] = nums[j]
nums[j] = temp
falies = 0
for i in range(len(nums)-1):
if nums[i] > nums[i+1]:
falies += 1

if falies > 0:
return False
else:return True

[randomshorts]

15:47 [2, 2, 2, 1, 1, 1] can be sorted, we can swap.

[treelibrarian]

So I think theres a slightly easier way to think of it than subarrays, which produces a slightly simpler and more optimal solution:
Since in sorting every element must pass every element that is before it which is not less than it, for each element you only have to test that it is not less than the previous maximum element of a different popcnt(). While we are scanning the array, we keep just the current maximum, the last element's popcnt(), and the maximum from the previous popcnt():


def sortable(arr):
cmax =
lmax = cmax
pp = 65

for a in arr:
p = popcnt64(a)
if pp != p: lmax = cmax # we changed popcnt, the max of the last popcnt is now what was the current max
if a < lmax: return False # we check if the current value is less than the max of a different popcount, and fail if so.
if cmax < a: cmax = a # we update the current max with the new value if appropriate
pp = and keep the popcnt for the next elements test

return True

def bitwise algorithm for popcnt: should be (much) quicker than loop based or string conversion.
access to the CPU's hardware popcnt instruction through a C extension would be even better.
vs = val >> 1
val &= make 2 bits available for sum of each pair
vs &=
val += sums of 2 bits, max = 2

vs = val >> 2
val &= make 4 bits available for each sum
vs &=
val += sums of 4 bits, max = 4, 3 bits required

vs = val >> 4
val += sums of 8 bits, max = 8, 4 bits required

vs = val >> 8
val &= 0x000f000f000f000f # make 16 bits available for each sum (and remove extra sums)
vs &= 0x000f000f000f000f
val += of 16 bits, max = 16, 5 bits required 16 available

val += val >> no further filters required
val += val >> 32

return val & until here

[shauryatomer]

thanks for the awesome explanation and daily uploading POTD solutions

[petercollins]

Thank you for all your videos NeetCode. They have helped me a ton! When you implemented count_bits from scratch I don’t think it was correct. It seems like it would return if the MSB of n is a 1 or not when it’s supposed to count the bit’s set to 1 in n. I think it should have been res += n & 1 instead of res = n & 1. Cheers.

[bananesalee]

interesting problem, it definitely looked harder than it is

[WaiyatIntellectual]

So, [2, 2, 2, 1, 1, 1] never hitting the else part is correct but Neetcode makes an assumption that it will hit "if prev_max > curr_min: return False " which it never does, it is a True testcase as the array is sortable. So, when the numbers in the entire array has same number of set bits they can always be sorted by swapping. A good example would be [3, 16, 8, 4, 2] instead where after code finishes running on the [16, 8, 4, 2] part and would return true if the above mentioned line of code wasn't there. So, correct explanation would be if there is no third set of numbers to go through then we need to check if max from first set isn't greater than the min from second set which is an edge case for the second solution.

[XGKQJ]

What an amazing approach... How do you come up with it

[LeetCodeUzbekistan]

I gotta comment this out, thank you bro, you're doing a really good job, Idk if there is a way for donation, I been following you around for a year, now I work in a big company which is Yandex, you helped me grew up so much

[MehmetDemir-xiyy]

We don't have to swap elements. Just check counts if does not match return false