Coding Problem 5

-
        Lowest Missing Positive Integer
                                                                          asked by Stripe

Ques. Given an array of integers, find the first missing positive integer in the linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.

For example - the input [3, 4, -1, 1] should give 2 and input [1, 2, 0] should give 3.

Solution. 
This problem can be solved by many ways but here we have to keep in mind about the contraints of complexity. We can not use extra space and time can not be more than O(n). 
What we can do here ? Well there is an idea. Firstly we separate out positive and negative integers in the array and we can do this inplace. Whever we see the non-positive number we swap it with the first positive number in the array. We also have to count the non-negative numbers. After separating suppose we get the array like this -

[-1, 4, 3, 1] and count is 1.

Now we divide our array and keep only positive numbers greater than 0. Now we can traverse the array and mark the presence of element in the array by changing the sign of value at the index equal to element. It means that for element x we change the sign of element at index x in the array.Then we can again traverse the array and print the index at which we get first positive value. We have to keep in mind here about the indexing, since indexing start from 0 so always print the index+1 value and if no positive value is present then we print the value next to the size of array. Lets see the code here -

inp = [3, 4, -1, 1]      # our input
size = len(inp)          # size of input array

def segregate(arr, size):
    j = 0
    for i in range(size):
          # if value is 0 or negative
 if arr[i] <= 0:
    arr[i], arr[j] = arr[j], arr[i]   # swap with first positive in array
    j += 1   # couter to keep the number of shifts (number of non-positive integers)
    return j

def findMissing(arr, size):
    # traverse the array and mark the element at index equal to current element negative, here we are subtracting 1 because index starts from 0.
    for i in range(size):
if (abs(arr[i]) - 1 < size and arr[abs(arr[i]) - 1] > 0):
    arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]

    # Return index of first positive value and add 1 to the index because index starts from 0
    for i in range(size):
if arr[i] > 0:
    return i+1
    return size+1     

shifts = segregate(inp, size)
result = findMissing(inp[shifts:], size - shift )
print(result)

Output: 2

Comments

Post a Comment

Popular posts from this blog

Coding Problem 10

-
Image
                                Minimum Cost Required                                                        asked by Facebook Ques. A builder is looking to build a row of N houses that can be of K different colors. He has a goal of minimizing cost while ensuring that no two neighbouring houses are of same color. Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth color return the minimum cost which achieves this goal. Solution.   Suppose we have cost matrix like this - [ [2, 1, 1],   [1, 10, 3],   [1, 2, 100]  ] Each row represents the house and each column represents the color so the values are the cost of painting the color for a house. Since we know that indexes starts from 0 so cost of pain...
Read more

Coding Problem 3

-
             Sum of Numbers in List                                                      asked by Google Ques. Given a list of numbers and a integer K return whether any two numbers from the list will add upto K or not. For example - Given list is [10, 15, 3, 7] and K = 17, then return True because 10 + 7 = 17. Solution.   So basically we have to find the two numbers that are present in the list and sum of both is equal to K. So we can simply run two loops on the list and check each pair of number if they are equal to K or not. This method is Brute-force and complexity is O(n^2). What we can do here is run the loop over the list and then subtract that number from the target and check whether the remaining number is present in the list or not. Lets see the code  def find_numbers(inp_list, K):    ...
Read more

Coding Problem 9

-
                                    Maximum in Subarray                                                          asked by Google Ques. Given an array of integers and a number k, where 1<= k <= length of array, compute the maximum values of each subarray of length k. For example - given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get [10, 7, 8, 8], since  10 = max(10, 5, 2) 7 = max(5, 2, 7) 8 = max(2, 7, 8) 8 = max(7, 8, 7) Solution. This question has a simple solution. In array we will create a window which consist of number of elements equal to k and can find the maximum among them and append that in output list. But while traversing the array we have to keep something very important in mind. We will not traverse from index 0 to nth index...
Read more