Coding Challenge — 1
This problem was recently asked by Google
Given a list of numbers with only 3 unique numbers (1, 2, 3), sort the list in O(n) time.
Example 1:
Input: [3, 3, 2, 1, 3, 2, 1]
Output: [1, 1, 2, 2, 3, 3, 3]def sortNums(nums):
# Fill this in.print sortNums([3, 3, 2, 1, 3, 2, 1])
# [1, 1, 2, 2, 3, 3, 3]
Challenge: Try sorting the list using constant space.
Solution1:
def sortNums(nums):
#print(nums)
a = 0
b = 0
c = 0for i in nums:
if i == 1:
a += 1
elif i == 2:
b += 1
else:
c += 1
return [1] * a + [2] * b + [3] * cprint(sortNums([3, 3, 2, 1, 3, 2, 1]))
# [1, 1, 2, 2, 3, 3, 3]
Solution2:
The time complexity of O(n), the space complexity is O(1)
def sortNums(nums):
one_idx = 0
three_idx = len(nums) - 1
idx = 0while idx < three_idx:
if nums[idx] == 1:
nums[idx], nums[one_idx] = nums[one_idx], nums[idx]
idx += 1
one_idx += 1
elif nums[idx] == 2:
idx += 1
else:
nums[idx], nums[three_idx] = nums[three_idx], nums[idx]
three_idx -= 1
return numsprint(sortNums([3, 3, 2, 1, 3, 2, 1]))
# [1, 1, 2, 2, 3, 3, 3]
