Find if Array Can Be Sorted - Leetcode 3011 - Python

[@michaelmcmanus2703]

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

[@brendanfay9786]

great work

[@caresword]

@@brendanfay9786 thank you. felt really good

[@treelibrarian7618]

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 = -2000000000 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 = p # and keep the popcnt for the next elements test return True def popcnt64(val): # 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 &= 0x5555555555555555 # make 2 bits available for sum of each pair vs &= 0x5555555555555555 val += vs # sums of 2 bits, max = 2 vs = val >> 2 val &= 0x33333333333333333 # make 4 bits available for each sum vs &= 0x33333333333333333 val += vs # sums of 4 bits, max = 4, 3 bits required vs = val >> 4 val += vs # 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 += vs # of 16 bits, max = 16, 5 bits required 16 available val += val >> 16 # no further filters required val += val >> 32 return val & 63 # until here

[@randomshorts5200]

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

[@MP-ny3ep]

Very beautifully explained. Thank you

[@petercollins7873]

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.

[@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.

[@shauryatomer1058]

thanks for the awesome explanation and daily uploading POTD solutions

[@bananesalee7086]

interesting problem, it definitely looked harder than it is

[@X7G9K2QJ]

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

[@abhinavchoukse2357]

@@eamytb @X7G9K2QJ well, I came up with both approaches myself ...so I think it's not that hard to come by yourself if you have practiced enough question

[@devmahad]

thanks :)

[@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

[@georgetan5256]

be a member of his main channel, 5 dollars a month, you are welcome

[@MehmetDemir-xi3yy]

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

[@web-unlocked]

hello goat

[@MrAg1980]

2nd

[@piyushchauhan2898]

Why are you using python 😕

[@Akash.B28]

whats your familiar language

[@piyushchauhan2898]

@Akash.B28 java

[@Axel.Blazer]

wdym💀

[@me.sharmashubam]

☠️☠️

[@nizh3278]

@@piyushchauhan2898 noice !!