Solving The Coding Question From Amazon Interview

Solving A Question That Was Asked In The Technical Round At Amazon

Photo by John Schnobrich on Unsplash

So last week I gave an interview at Amazon for SDE 6M internship program. It was the technical round of the entire process, and there were two coding questions in that round.

I’m going to explain one of the coding questions and how I solved it here.

The question was similar to the DNF(Dutch National Flag)/Sort Colors problem, but the data was changed.

Question

Given an array of integers and a target value, return the array such that the values that are less than the target should be on the left side of the array, and values that are greater than the target should be on the right side of the array. Values that are equal to the target should be in between other values.

Example:

Input: nums = [9, 12, 5, 10, 14, 3, 10], target = 10
Output: [9, 5, 3, 10, 10, 12, 14]
Input: nums = [-3, 4, 3, 2], target = 2
Output: [-3, 2, 4, ]

Solution

Approach 1:

At first, we started with designing an algorithm and describing the thought process of how we are going to solve this problem.

In the first approach, I designed the following code. But the problem with this code was that we were using O(n) extra space and values in the output were not in the same order as the original array.

Code:

def solve1(nums, target):
    i, j = 0, len(nums) - 1
    output = [target] * len(nums)
    for k in range(len(nums)):
        if nums[k] < target:
            output[i] = nums[k]
            i += 1
        elif nums[k] > target:
            output[j] = nums[k]
            j -= 1
    return output

The space complexity of this program will be O(n) because we are using extra space, and time complexity will be O(n).

Approach 2:

Then the interviewer asked me to solve this problem in place.

The idea is to create two pointers i, j, and initialize them to 0 and 1. We are going to create two passes, in the first pass we will put the values that are smaller than the target will be on the left side and in the next pass put the values that are greater than x on the right side of the array.

In the first pass, we check if the value is smaller than the target if it’s smaller then we just increase the value of i by 1. If the first condition failed, then we will check if the value at the jth index is smaller than the target, if it is smaller than the target then we are going to swap values at the ith and jth index and increase the i by one.

Every time, we are going to increase the value of j by 1.
If the value of j becomes equal to the length of the array, then we will break out of the loop.

We will decrease the value of j by 1, so it can become equal to the length of the array.
We will do the same for values that are greater than the target, but conditions will be reversed, and the loop only runs until i will be less than j.

Code:

def solve(nums, target):
    i, j = 0, 1
    while j < len(nums):
        if nums[i] < target:
            i += 1
        elif nums[j] < target:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
        j += 1
    j -= 1
    while i < j:
        if nums[j] > target:
            j -= 1
        elif nums[i] > target:
            nums[i], nums[j] = nums[j], nums[i]
            j -= 1
        i += 1

The space complexity of this program will be O(1) because we are doing it in-place, and time complexity will be O(n).

Let me know if we can optimize it more. Subscribe to the email newsletter for more technical content.