Questions

Given a sorted array of numbers, find if a given number ‘key’ is present in the array. Though we know that the array is sorted, we don’t know if it’s sorted in ascending or descending order. You should assume that the array can have duplicates. Write a function to return the index of the ‘key’ if it is present in the array, otherwise return -1.

Example 1:

Input: [4, 6, 10], key = 10
Output: 2

Example 2:

Input: [1, 2, 3, 4, 5, 6, 7], key = 5
Output: 4

Example 3:

Input: [10, 6, 4], key = 10
Output: 0

Example 4:

Input: [10, 6, 4], key = 4
Output: 2

Implementation: OrderAgnosticBinarySearch

  1. First we need to determine the sort order. To do that, we check the first and last numbers and if first number is lesser than last, its in ascending order, else descending.
  2. Then we do a binary search to find the key.
  3. Since its not said which key to return in case of duplicates, we will return any key.

Time complexity

O(logn)

Space complexity

O(1)

Given an array of numbers sorted in an ascending order, find the ceiling of a given number ‘key’. The ceiling of the ‘key’ will be the smallest element in the given array greater than or equal to the ‘key’. Write a function to return the index of the ceiling of the ‘key’. If there isn’t any ceiling return -1.

Example 1:

Input: [4, 6, 10], key = 6
Output: 1
Explanation: The smallest number greater than or equal to '6' is '6' having index '1'.

Example 2:

Input: [1, 3, 8, 10, 15], key = 12
Output: 4
Explanation: The smallest number greater than or equal to '12' is '15' having index '4'.

Example 3:

Input: [4, 6, 10], key = 17
Output: -1
Explanation: There is no number greater than or equal to '17' in the given array.

Example 4:

Input: [4, 6, 10], key = -1
Output: 0
Explanation: The smallest number greater than or equal to '-1' is '4' having index '0'.

Implementation: CeilingOfNumber

There are two conditions here:

  1. Key is equal to a candidate element. In that case we return the index of the candidate.
  2. Candidate element is lesser than key and is such that there is no other element lesser than key. We can check for this case by: 2.1 When we encounter a candidate smaller than key, we check the next element. If the next element is greater than key, that is our solution. 2.2 If there is no next element, there is no solution.
  3. One thing to look out for is what happens if the key is smaller than the smallest element in the array. In that case, it will never find a candidate which can satisfy the condition and we can return index 0.

Time complexity

O(logn)

Space complexity

O(1)

Given an array of lowercase letters sorted in ascending order, find the smallest letter in the given array greater than a given ‘key’. Assume the given array is a circular list, which means that the last letter is assumed to be connected with the first letter. This also means that the smallest letter in the given array is greater than the last letter of the array and is also the first letter of the array. Write a function to return the next letter of the given ‘key’.

Example 1:

Input: ['a', 'c', 'f', 'h'], key = 'f'
Output: 'h'
Explanation: The smallest letter greater than 'f' is 'h' in the given array.

Example 2:

Input: ['a', 'c', 'f', 'h'], key = 'b'
Output: 'c'
Explanation: The smallest letter greater than 'b' is 'c'.

Example 3:

Input: ['a', 'c', 'f', 'h'], key = 'm'
Output: 'a'
Explanation: As the array is assumed to be circular, the smallest letter greater than 'm' is 'a'.

Example 4:

Input: ['a', 'c', 'f', 'h'], key = 'h'
Output: 'a'
Explanation: As the array is assumed to be circular, the smallest letter greater than 'h' is 'a'.

Implementation: NextLetter

    key = 'f' 
        0       1       2       3
        'a'     'c'     'f'     'h'
        l       m                h      

        mid = 0 + (3-0)/2 = 1         

        key >= arr[mid], low = mid+1

        0       1       2       3
        'a'     'c'     'f'     'h'
                        l        h 
                        m
        mid = 2 + (3-2) / 2 = 2

        key >= arr[mid], low = mid+1

        0       1       2       3
        'a'     'c'     'f'     'h'
                                l / h 
                        m
        mid = 3 + (3-3) / 2 = 3

        key < arr[mid], high = mid-1 (2)

        loop terminates, because low > high

We have to find the smallest number which is greater than key.

  1. So if key is smaller than mid, the number must lie towards the left, else towards the right.
  2. The next letter will be the position of low. Why? - Since, we are narrowing down our low->high range, till low>high, low+1 would be the "next" number.
  3. However, this is a circular array, so if low was the last element index=arr.length-1, it would overflow the array. Thus, we mod it, so it return index 0.

Time complexity

O(logn)

Space complexity

O(1)

Search infinite sorted array

Given an infinite sorted array (or an array with unknown size), find if a given number ‘key’ is present in the array. Write a function to return the index of the ‘key’ if it is present in the array, otherwise return -1.

Since it is not possible to define an array with infinite (unknown) size, you will be provided with an interface ArrayReader to read elements of the array. ArrayReader.get(index) will return the number at index; if the array’s size is smaller than the index, it will return Integer.MAX_VALUE.

Example 1:

Input: [4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30], key = 16
Output: 6
Explanation: The key is present at index '6' in the array.

Example 2:

Input: [4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30], key = 11
Output: -1
Explanation: The key is not present in the array.

Example 3:

Input: [1, 3, 8, 10, 15], key = 15
Output: 4
Explanation: The key is present at index '4' in the array.

Example 4:

Input: [1, 3, 8, 10, 15], key = 200
Output: -1
Explanation: The key is not present in the array.

Implementation: SearchSortedInfiniteArray

Here, the issue with doing binary search is we dont know the high, since there could be an infinite amount of numbers. Since we dont know, its reasonable to start with either a random number or a really high number.

Once we start with a number, then we follow regular binary search till we either get the key or run out of numbers.

This can be optimized if we knew the distribution of the numbers, but since that's not the case, a random number is as good as any.

Time complexity

O(logn)

Space complexity

O(1)

Given an array of numbers sorted in ascending order, find the element in the array that has the minimum difference with the given ‘key’.

Example 1:

Input: [4, 6, 10], key = 7
Output: 6
Explanation: The difference between the key '7' and '6' is minimum than any other number in the array 

Example 2:

Input: [4, 6, 10], key = 4
Output: 4

Example 3:

Input: [1, 3, 8, 10, 15], key = 12
Output: 10

Example 4:

Input: [4, 6, 10], key = 17
Output: 10

Implementation: MinDiffElement

If the key is present in the array, then that number is the one with the minimum difference of 0. If we dont, then the low and high positions are the two candidates for the min. We will return whichever has the min diff.

Time complexity

O(logn)

Space complexity

O(1)

Find the maximum value in a given Bitonic array. An array is considered bitonic if it is monotonically increasing and then monotonically decreasing. Monotonically increasing or decreasing means that for any index i in the array arr[i] != arr[i+1].

Example 1:

Input: [1, 3, 8, 12, 4, 2]
Output: 12
Explanation: The maximum number in the input bitonic array is '12'.

Example 2:

Input: [3, 8, 3, 1]
Output: 8

Example 3:

Input: [1, 3, 8, 12]
Output: 12

Example 4:

Input: [10, 9, 8]
Output: 10

Implementation: BitonicArrayMax

There are 2 parts to the bitonic array: an ascending part and a descending part.

Time complexity

O(logn)

Space complexity

O(1)

Given a Bitonic array, find if a given ‘key’ is present in it. An array is considered bitonic if it is monotonically increasing and then monotonically decreasing. Monotonically increasing or decreasing means that for any index i in the array arr[i] != arr[i+1]. Write a function to return the index of the ‘key’. If the ‘key’ is not present, return -1.

Example 1:

Input: [1, 3, 8, 4, 3], key=4
Output: 3

Example 2:

Input: [3, 8, 3, 1], key=8
Output: 1

Example 3:

Input: [1, 3, 8, 12], key=12
Output: 3

Example 4:

Input: [10, 9, 8], key=10
Output: 0

Implementation: SearchBitonicArray

Based on the previous problem, we know:

  1. If arr[mid] > arr[mid+1], the we are in the decreasing range.
  2. If arr[mid] < arr[mid+1], we are in the increasing range.

Based on which range we are in, we then, can move low and high to either left or right of mid.

Time complexity

O(logn)

Space complexity

O(1)

Given an array of numbers which is sorted in ascending order and also rotated by some arbitrary number, find if a given ‘key’ is present in it. Write a function to return the index of the ‘key’ in the rotated array. If the ‘key’ is not present, return -1. You can assume that the given array does not have any duplicates.

Example 1:

Input: [10, 15, 1, 3, 8], key = 15
Output: 1
Explanation: '15' is present in the array at index '1'.

Example 2:

Input: [4, 5, 7, 9, 10, -1, 2], key = 10
Output: 4
Explanation: '10' is present in the array at index '4'.

Implementation: SearchRotatedArray

When we select a mid, one of two things can happen:

  1. Left side is sorted in ascending order.
  2. Right side is sorted in ascending order because of the rotation.

We can check this by comparing low to mid. If low is <= mid, then from low to mid, aka, the left side is in ascending order.

Else, since the left side is not in ascending order, and because there can be only one rotation, the right side must be in ascending order.

Based on the value of key and mid, we can now move our low and high accordingly.

Time complexity

O(logn)

Space complexity

O(1)

Given an array of numbers which is sorted in ascending order and is rotated ‘k’ times around a pivot, find ‘k’. You can assume that the array does not have any duplicates.

Example 1:

Input: [10, 15, 1, 3, 8]
Output: 2
Explanation: The array has been rotated 2 times.
Example 2:

Input: [4, 5, 7, 9, 10, -1, 2]
Output: 5
Explanation: The array has been rotated 5 times.
Example 3:

Input: [1, 3, 8, 10]
Output: 0
Explanation: The array has been not been rotated.

Implementation: RotationCount

What does rotation mean? For this array

[10, 15, 1, 3, 8]

The sorted variant would be:

[1, 3, 8, 10, 15]

To move, 10 and 15 to index 0 and 1 respectively, we would need to make 2 movements.

For

[4, 5, 7, 9, 10, -1, 2]

The sorted array is:

[-1, 2, 4, 5, 7, 9, 10]

We have to move 4, 5, 7, 9, 10, aka, 5 numbers to get to the current set of rotations.

In other words, if we substract the number of elements that are in the original order (without rotation) from the length of the array, we will get the number of rotated elements, aka, the number of rotations.

How do we do that?

We need to find an element whose next element is less than the current element. That element must me the start of non-rotated elements.

We can do a regular binary search and if mid > mid+1, mid+1 must be the start of non-rotated sub-array.

Time complexity

O(logn)

Space complexity

O(1)

Return to Index