Skip to content

Instantly share code, notes, and snippets.

@manojnaidu619
Created April 9, 2020 14:45
Show Gist options
  • Save manojnaidu619/c5007db8611251d57ee0d3c38c8864d8 to your computer and use it in GitHub Desktop.
Save manojnaidu619/c5007db8611251d57ee0d3c38c8864d8 to your computer and use it in GitHub Desktop.
sort binary array in linear time
nums = [0, 0, 1, 0, 1, 1, 0, 1, 0, 0] # change the array here
i,j=0,len(nums)-1
zeroes, ones = 0,0
flag=0
while i<=j:
if nums[i]==0:
zeroes+=1
else:
ones+=1
if nums[j]==0:
zeroes+=1
else:
ones+=1
i+=1
j-=1
j=i+1
while 1:
if flag == 2: break
nums[i]=0
nums[j]=1
i-=1
j+=1
if i<0: flag+=1
if j>=len(nums)-1: flag+=1
print(nums)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment