CA 08 - Sort 0s, 1s, and 2s

 Sort 0s, 1s and 2s

Given an array arr[] containing only 0s, 1s, and 2s. Sort the array in ascending order.

Note: You need to solve this problem without utilizing the built-in sort function.
Input: arr[] = [0, 1, 2, 0, 1, 2]
Output: [0, 0, 1, 1, 2, 2]
Explanation: 0s, 1s and 2s are segregated into ascending order.
Input: arr[] = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
Output: [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]
Explanation: 0s, 1s and 2s are segregated into ascending order.
Expected Complexities
Time Complexity: O(n)
Auxiliary Space: O(1)

CODE:
    The initial approach of solving this problem, was using the appropriate sorting method to sort the given array. Given that the expected Auxiliary space as O(1), the array should be sorted in place, thus quick sort is used. 
class Solution:
    def sort012(self,arr):
        def quicksort(arr, first, last):
            if first < last:
                pivot = first
                i = first
                j = last
       
                while i < j:
                    while i < len(arr) and arr[i] <= arr[pivot]:
                        i += 1
                    while arr[j] > arr[pivot]:
                        j -= 1
       
                    if i < j:
                        arr[i], arr[j] = arr[j], arr[i]
       
                arr[pivot], arr[j] = arr[j], arr[pivot]
                quicksort(arr, first, j - 1)
                quicksort(arr, j + 1, last)
               
        quicksort(arr,0,len(arr)-1)

 but here the time complexity for worst case will be O(n^2), thus only 1010 testcases passed and hit a time limit exceed. 

    Approaching this problem with tim sort will make the problem to be solved with the above constraints. The other method is to approach this with Dutch National Flag algorithm, which is pretty much closer to quicksort

class Solution:
    def sort012(self,arr):
        low = 0
        mid = 0
        high = len(arr) - 1
   
        while mid <= high:
            if arr[mid] == 0:
                arr[low], arr[mid] = arr[mid], arr[low]
                low += 1
                mid += 1
            elif arr[mid] == 1:
                mid += 1
            else:
                arr[mid], arr[high] = arr[high], arr[mid]
                high -= 1
   

Comments

Post a Comment

Popular posts from this blog

CA 04 - Two Sum & Sorted Two Sum

Image
  MY CODE: In brute force method the intuitive way of solving this problem with two for loop. Using nested loop to traverse through the list and try different combination of two sum to check if it matches with the target.    Time complexity: O(n^2)       OPTIMIZED:          In the optimized method of approaching the Two Sum problem. The given list is already sorted in ascending order. This gives us the leverage of using Two pointer technique to solve this problem. Thus using single loop to approach this problem. If current sum is less than target move the left pointer, if it is greater move the right pointer else return the current index (equal to target).  Time complexity: O(n) MY CODE:
Read more

CA 05 - Reverse the array

  Array Reverse Reverse an array  arr[] . Reversing an array means  rearranging  the elements such that the  first  element becomes the  last , the  second  element becomes  second last  and so on. Input: arr[] = [1, 4, 3, 2, 6, 5] Output: [5, 6, 2, 3, 4, 1] Explanation: The first element 1 moves to last position, the second element 4 moves to second-last and so on. Input: arr[] = [4, 5, 1, 2] Output: [2, 1, 5, 4] Explanation: The first element 4 moves to last position, the second element 5 moves to second last and so on. CODE:     BRUTE FORCE METHOD:          Here, in this method we will create a temporary array to store the reversed given array and then assign it to the given array class Solution :     def reverseArray ( arr ):         n = len (arr)         temp = [ 0 ] * n         for i in range (n- 1 ,- 1 ,- 1 ): ...
Read more

CA 21 - Basic Select SQL Queries

Image
 1.  Query all columns for a city in   CITY   with the   ID   1661 . The  CITY  table is described as follows: Here we make use of the where conditon cllause to retrieve the details of the Id with 1661, we select all the columns to be displayed and "*" is avoided for best practice. SOLUTION: SELECT ID,NAME,COUNTRYCODE,DISTRICT,POPULATION FROM CITY where ID = 1661 ; 2. Query all columns for all American cities in the   CITY   table with populations larger than   100000 . The   CountryCode   for America is   USA . The  CITY  table is described as follows: Here we make use of the where condtional clause, to obatin the population to be over thhe given number we make use of the' >' symbol to achieve this. Also the AND operator is used to state two where conditons where we want only the details of cities in USA so we use the countrycode check with 'USA' single quotes are used to check with the value, usage ...
Read more