16 JavaScript Intermediate Level Binary Search Interview Questions & Answers

Below is a list of our JavaScript Intermediate Level Binary Search interview questions. Click on any interview question to view our answer advice and answer examples. You may view 5 answer examples before our paywall loads. Afterwards, you'll be asked to upgrade to view the rest of our answers.

1. What is the smallest divisor with a given limit.

This question focuses on the developer's knowledge of JavaScript binary search and arrays.

You are given an array of integer nums and an integer limit. You will choose an integer divisor, divide all the integers of nums by divisor, and will add the divisionsâ€™ result. Find the smallest divisor such that the sum is less than or equal to the limit.

The result of a division is rounded to the nearest integer greater than the actual real result (i.e ceil of the division). For example:- 17 / 3 = 6, and 30 / 6 = 5.

/*Example*/

nums = [1, 2, 5, 9]		limit = 6
expected output = 5
explanation:
â—	if the divisor were smaller (say 4), the sum after division would be 7 (1 + 1 + 2 + 3) which is greater than limit.
â—	if the divisor were greater (say 6), the sum after division would be 5 (1 + 1 + 1 + 2) which is smaller than limit.

Solution:

We can use binary search. Letâ€™s say min is the smallest divisor required. There are two observations:

â— Given a divisor smaller than min, the sum after division will always be greater than the limit.
â— Given a divisor larger than or equal to min, the sum after division will always be less than or equal to the limit.

divisors- 1 2 â€¦ min min + 1 min + 2 max-divisor
is sum F F F T T T T
less than
or equal
to limit

/**
 * @param {number[]} nums
 * @return {number}
 */
function findMinimumEffort(nums, limit) {
    let left = 1
    let right = Math.max(...nums)
    
    while(left < right) {
        let mid = (left + right) / 2
        mid = Math.floor(mid)
        
        // is sum less than or equal to limit        
        if (isLessOrEqLimit(mid, nums, limit)) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return left
}

function isLessOrEqLimit(divisor, nums, limit) {
    let sum = 0
    
    for (const num of nums) {
        let quotient = num / divisor
        quotient = Math.ceil(quotient)
        sum += quotient
    }
    
    return sum <= limit
}

Time complexity- O(n log (max number))
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

2. What are the minimum number of days to make bouquets?

This question focuses on the developer's knowledge of JavaScript binary search and loops.

You own a garden which has flowers arranged in a row. The flowers have not bloomed yet. You need to make m bouquets. To make one bouquet, you need k adjacent flowers from the garden. For the ith flower, the adjacent flowers are (i - 1)th and (i + 1)th flowers.
The garden has n flowers. You are given an array bloomDay of size n. The ith flower will bloom on day bloomDay[i]. One flower can be used to make at most one bouquet.
Your task is to find the minimum number of days you need to wait so that enough flowers have bloomed to make m bouquets. If it is impossible to make m bouquets, return -1.

/*Example*/

bloomDay = [1, 10, 3, 10, 2]	m = 3		k = 1
expected output = 3
explanation:- x represents that the flower at that position has bloomed
after day 1:- [x, _, _, _, _]
after day 2:- [x, _, _, _, x]
after day 3:- [x, _, x, _, x]	After 3 days, we can make 3 bouquets.

Solution:

We can use binary search for it. Letâ€™s say min is the minimum of days required. If we are asked:
â— Can we make m bouquets in days less than min? The answer is definitely no.
â— Can we make m bouquets in days greater than or equal to min? The answer is definitely yes.

0 1 â€¦ min - 1 min min + 1 â€¦ max-possible
F F F F T T T T

We can do the binary search from 0 to max-possible. We will check if we can make m bouquets in a mid number of days or not. We will update the variables accordingly as in the code. The value of max-possible is the maximum of bloomDay array i.e. the maximum number of days that a flower will take to bloom.

To check if we can make m bouquets in a mid number of days or not, we will use canMake function. We will see which flowers will bloom on or before the day days. After checking bloomed flowers, we see the number of adjacent flowers and then count the number of bouquets that can be formed using those adjacent flowers.

/**
 * @param {number[]} bloomDays
 * @param {number} m
 * @param {number} k
 * @return {number}
 */
function minDays(bloomDays, m, k) {
    // there are not enough flowers
    if (m * k > bloomDays.length) {
        return -1
    }
    
    let left = 1;
    let right = Math.max(...bloomDays)
    
    while(left < right) {
        let mid = (left + right) / 2
        mid = Math.floor(mid)
        
        if (canMake(mid, bloomDays, m, k)) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return left
}

function canMake(days, bloomDays, m, k) {
    let bouquetsMade = 0
    let adjFlowers = 0
    
    for (const day of bloomDays) {
        // the current flower has not
        // bloomed yet before or on `day`
        if (day > days) {
            adjFlowers = 0
            continue
        }
        
        // the flower has bloomed
        bouquetsMade += Math.floor((adjFlowers + 1) / k)
        adjFlowers = (adjFlowers + 1) % k
        
    }
    
    return bouquetsMade >= m
}

Time complexity- O(n log (max-possible))
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

3. How can you minimize the maxOperations penalty?

This question focuses on the developer's knowledge of JavaScript functions and binary search.

There are n bags. Each bag contains some number of balls given by array nums. The ith bag contains nums[i] number of balls. You need to do some operations on the array. In one operation, you take a bag and divide it into two bags containing a positive number of balls. For example, if you had a bag with 6 balls, you can do one operation and divide it into two bags containing 2 and 4 balls. You are also given an input parameter maxOperations which is the maximum number of operations that you can perform.

The penalty on all the bags is the maximum number of balls in a bag. Your task is to minimize the penalty in maxOperations number of operations.

/*Example*/

nums = [7, 6, 17]		maxOperations = 2
expected output = 7
explanation:-
after first operation:- [7, 6, 7, 10]
after second operation:- [7, 6, 7, 7, 3]
the maximum number of balls is 7. So the penalty is 7.

Solution:

We can use binary search for it. Letâ€™s say min is the minimum penalty that is possible using maxOperations. If we are asked:
â— Can we have a penalty of less than min? The answer is no.
â— Can we have a penalty greater than or equal to min? The answer is definitely yes.

1 2 â€¦ min - 1 min min + 1 â€¦ max-possible
F F F F T T T T

We will do the binary search from 1 to max-possible. The value of max-possible is the maximum penalty that we can have which is the penalty before any operation. The function canDo returns if we can have a penalty using maxOperations.

/**
 * @param {number[]} nums
 * @param {number} maxOperations
 * @return {number}
 */
function minimumPenalty(nums, maxOperations) {
    let left = 1
    let right = Math.max(...nums)
    
    while(left < right) {
        let mid = (left + right) / 2
        mid = Math.floor(mid)
        
        if (canDo(mid, nums, maxOperations)) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return left
}

function canDo(penalty, nums, maxOperations) {
    let operationsCount = 0
    
    for (const num of nums) {
        let count = num / penalty
        count = Math.ceil(count) - 1
        operationsCount += count
    }
    
    return operationsCount <= maxOperations
}

Time complexity- O(n log (max-possible))
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

4. Create a key-value store with timestamp.

This interview question focuses on the developer's understanding of JavaScript methods and their uses.

You have to implement a class TimeMap. There are two methods in this class: set and get. The class is a key-value store with associated timestamps.

=> The method set is called with three parameters:- key, value, and timestamp. The store stores these passed parameters in a data structure in the class. It returns no value.
=> The get method is called with two parameters: key and timestamp. This method retrieves the latest value corresponding to the key before the timestamp. If there is no such value, it returns the empty string â€œâ€.

/*Example*/

Calls:

initialize TimeMap
.set("foo", "bar", 1)
.get("foo", 1)			// returns â€œbarâ€
.get("foo", 3)			// returns â€œbarâ€
.set("foo", "bar2", 4)
.get("foo", 4)			// returns â€œbar2â€
.get("foo", 5)			// returns â€œbar2â€

Calls:

initialize TimeMap
.set("love", "high", 10)
.set("love", "low", 20)
.get("love", 4)			// returns â€œâ€
.get("love", 10)			// returns â€œhighâ€
.get("love", 15)			// returns â€œhighâ€
.get("love", 20)			// returns â€œlowâ€
.get("love", 25)			// returns â€œlowâ€
.set("super", "high", 30)
.get("super", 30)		// returns â€œhighâ€
.get("super", 1)			// returns â€œâ€

Constraint: The value of timestamps for each get method call will be strictly increasing.

class TimeMap {
    /**
     * Initialize your data structure here.
     */
    constructor() {
        // TODO
    }

    /** 
     * @param {string} key 
     * @param {string} value 
     * @param {number} timestamp
     * @return {void}
     */
    set(key, value, timestamp) {
        // TODO
    }

    /** 
     * @param {string} key 
     * @param {number} timestamp
     * @return {string}
     */
    get(key, timestamp) {
        // TODO
    }
}

Solution:

We will use a map to store keys and corresponding values and timestamps. We are naming the map 'store'. For each key in the map, we will have an array (we call this array timedValues). Each element of the timedValues is an array of size 2. The first element is a timestamp and the other is the corresponding value.

For example 1, the final store will be:-
{
â€œfooâ€ -> [[1, â€œbarâ€], [4, â€œbar2â€]]
}
For example 2, the final store will be:-
{
â€œloveâ€ -> [[10, â€œhighâ€], [20, â€œlowâ€]],
â€œsuperâ€ -> [[30, â€œhighâ€]],
}

The set method will push to timedValues corresponding to the given key.

The get method will get the timedValues array corresponding to the given key. Since timedValues are always sorted in increasing order, we can do a binary search over timedValues to find the value with the largest timestamp less than or equal or passed timestamp in the function.

There may be a case when we donâ€™t have a particular key in the store yet and we call either get or set for this key. We will create a helper function: getTimedValues. We will use this function to retrieve timeValues corresponding to that key. If the key already exists, we will return the timeValues straightway. If it doesnâ€™t, we first set an empty array corresponding to that key and then return it.

class TimeMap {
    /**
     * Initialize your data structure here.
     */
    constructor() {
        this.store = new Map()
    }
 
    /** 
     * @param {string} key 
     * @param {string} value 
     * @param {number} timestamp
     * @return {void}
     */
    set(key, value, timestamp) {
        const timedValues = this.getTimedValues(key)
        timedValues.push([timestamp, value])
    }
 
    /** 
     * @param {string} key 
     * @param {number} timestamp
     * @return {string}
     */
    get(key, timestamp) {
        const timedValues = this.getTimedValues(key)

        let left = 0
        let right = timedValues.length

        while(left < right) {
            let mid = (left + right) / 2
            mid = Math.floor(mid)

            if (timedValues[mid][0] > timestamp) {
                right = mid
            } else {
                left = mid + 1
            }
        }

        if (right === 0) return ""
        return timedValues[right - 1][1]
    }
    
    getTimedValues(key) {
        if (!this.store.has(key)) {
            this.store.set(key, [])
        }

        return this.store.get(key)
    }
}

Time complexity for constructor- O(1)
Space complexity for constructor- O(1)

Time complexity for one call of set- O(1)
Space complexity for one call of set- O(1)

Time complexity for one call of get- O(log n) // n is the maximum number of calls to set
Space complexity for one call of get- O(1)

Written by S. Kumar on May 22nd, 2021

5. Find a single occurring integer in the given sorted array.

This question shows the developer's ability to use JavaScript search effectively.

You are given sorted array nums. All the integers occur twice except one integer. Find the single occurring integer.

/*Example*/

Given nums = [1, 1, 2, 2, 3, 3, 4, 8, 8]
Expected output = 4

Solution:

Approach I (linear search):

The array is 0-indexed. So for the duplicate integers, if one integer is at even index, the next should be at odd index until the single integer is encountered.
integers:- |1 1| |2 2| |3 3| |4| |8 8|
indices:- |0 1| |2 3| |4 5| |6| |7 8|
pair pair pair single pair (odd-even)
(even-odd) (even-odd) (even-odd)

So we will iterate over the even indices and will compare its value with the value at the next odd index. If they are equal, we continue to look for the next odd index. If they are not equal, it means the integer at the current even index is the required single integer.

/**
 * @param {number[]} nums
 * @return {number}
 */
function findSingle(nums) {
    for (let i = 0; i < nums.length; i += 2) {
        if (nums[i] !== nums[i + 1]) {
            return nums[i]
        }
    }
}

Time complexity- O(n)
Space complexity- O(1)

Approach II (binary search):

Letâ€™s say the index of the single element is idx. From the above approach, it can be observed that:

For indices less than idx, the duplicate numbers are at even-odd indices, that is, the first duplicate is at an even index and the next duplicate is at the next odd index. Say these integers form the left partition.

For indices greater than idx, the duplicate numbers are at odd-even indices, that is, the first duplicate is at an odd index and the next duplicate is at the next even index. Say these integers form the right partition.

integers:- 1 1 2 2 3 3 4 8 8
indices:- 0 1 2 3 4 5 6 7 8
|<------------------------>| | |<--->|
left-partition single right-partition
integer

In such a scenario, we can use binary search. For the middle index mid, we will convert mid to an even index. Then we will compare it with integers at the next odd index, that is, we will compare nums[mid] with nums[mid + 1]. If they are equal, it means mid is an index of left-partition, so we will update left with mid + 2 (we are not updating it to mid + 1, because we already checked it). If they are not equal, it means mid is an index of right-partition, so we will update right to mid. After the loop, the left will be the index of the single number.

/**
 * @param {number[]} nums
 * @return {number}
 */
function findSingle(nums) {
    let left = 0
    let right = nums.length - 1
    
    while (left < right) {
        let mid = (left + right) / 2
        mid = Math.floor(mid)
        
        if (mid % 2 === 1) mid--
        
        if (nums[mid] !== nums[mid + 1]) {
            right = mid
        } else {
            left = mid + 2
        }
    }
    
    return nums[left]
}

Time complexity- O(log n)
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

6. What is the maximum value at a given index in a bounded array?

This question concentrates on the developer's skills with JavaScript elements.

You are given three positive integers n, index, and maxSum. Your task is to create new array nums of length n which satisfies the following conditions:

1. nums[i] > 0, for 0 <= i < n, that is, nums[i] is a positive integer;
2. abs(nums[i] - nums[i + 1]) <= 1, for 0 <= i < n, that is, the difference between two adjacent number must be at most 1;
3. the sum of all integers in nums is less than or equal to maxSum;
4. nums[index] is maximized.

Return the maximized integer nums[index]. It is guaranteed that the solution exists.

/*Example*/

Given:-
	n = 4
	index = 2
	maxSum = 6
Expected output:-2

Explanation: nums = [1, 2, 2, 1] is the array which satisfies all conditions. And nums[index] = 2. There is one more array nums = [1, 2, 2, 1] which satisfies all conditions with the same maximized nums[index] = 2.

Solution:

The value of each element in nums is at least 1. So we will subtract n (number of elements) from maxSum, so that the condition nums[i] > 0 is relaxed to nums[i] >= 0. We will see later the reason for doing this.

Let indexedValue be the value at index of nums, that is, indexedValue = nums[index]. Let maxIndexedValue be the maximum value of indexedValue possible which satisfies all the given four conditions. So if we are asked:

â— Is there an array num with indexedValue greater than maxIndexedValue such that it satisfies all the conditions except condition 4? The answer is definitely no.
â— Is there an array nums with indexedValue less than or equal to maxIndexedValue such that it satisfies all the conditions except condition 4? The answer is definitely yes.
In such a scenario, we can perform a binary search over the values of indexedValue. The values of indexedValue range from 0 to maxSum (after subtracting n). The binary search will help us to find indexedValue which satisfies condition 4. (say this task is #task_1)
Now, for a given value of indexedValue, we will try to generate an array nums (say this task is #task_2). The generated array must satisfy the first three conditions. We need to generate any one of that array such that its sum is less than or equal to maxSum. The Arithmetic Progression sequence on both sides is the optimal way to do this. For example, letâ€™s say index = 3, maxSum = 10, indexedValue = 4, n = 6
â— nums = 0 1 2 3 2 1
this is AP around the index 3 with value 3, the sum of the array is 9 which <= 10.
â— nums = 0 2 2 3 2 1
this is AP around the index 3 with value 3, the sum of the array is 10 which <= 10.
â— nums = 0 2 3 3 2 1
this is AP around the index 3 with value 3, the sum of the array is 11 which > 10.

When we select the array to be AP on both sides of the index, we can deterministically say that if the array is possible or not because there will be no other possible array with a sum less than the AP array.
We know, that if we are given the first and the last term of an AP, the sum of this AP is:-
sum = (first_term + last_term) * no_of_terms / 2

Thus for #task_2, we need not generate the whole array, actually. We need to find the first_term on both sides of indexedValue and sum them according to the above formula and check it against maxSum. Now take an example with indexedValue = 3, index = 5, and n = 7, the following is the array with AP:

nums = 0 0 0 1 2 3 2
indices = 0 1 2 3 4 5 6

On the right side, the first_term is 2. We can find it using:-
indexedValue - no_of_terms_on_right_side
= indexedValue - (n - 1 - index)

On the left side, the first_term is 1. We can find it using:-
indexedValue - no_of_terms_on_left_side
= indexedValue - index (this results in negative, so we can choose 0 instead.
= Math.max(indexedValue - index, 0)

Here it doesnâ€™t matter if the first term is 0 or 1. The sum remains the same. Thatâ€™s why we subtracted n from maxSum at the start of the solution to relax the condition 1 to include 0. So we will include the max thing to the right side too. So:

first_term_on_right_side = Math.max(indexedValue - (n - 1 - index), 0)
first_term_on_left_side = Math.max(indexedValue - index, 0)

/**
 * @param {number} n
 * @param {number} index
 * @param {number} maxSum
 * @return {number}
 */
function findMaxValue(n, index, maxSum) {
    maxSum -= n
    
    let left = 0
    let right = maxSum
    
    while (left < right) {
        let mid = (left + right + 1) / 2
        mid = Math.floor(mid)
        
        if (sumWithIndexedValue(mid, index, n) > maxSum) {
            right = mid - 1
        } else {
            left = mid
        }
    }
    
    return left + 1
}

function sumWithIndexedValue(indexedValue, index, n) {
    const leftMin = Math.max(indexedValue - index, 0)
    const leftSum = apSum(indexedValue, leftMin)
    
    const rightMin = Math.max(indexedValue - (n - 1 - index), 0)
    const rightSum = apSum(indexedValue, rightMin)
    return leftSum + rightSum - indexedValue
}

function apSum(a, b) {
    return (a + b) * (a - b + 1) / 2
}

Time complexity- O(log(maxSum))
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

7. Compare strings by frequency of the smallest character.

This question concentrates on JavaScript frequencies and sorting arrays.

Let f(str) frequency of the lexicographically smallest character in non-empty string str. For example f(â€œfbebâ€) = 2 because the lexicographically smallest character is â€œbâ€, which has a frequency of 2.

You are given two string array queries and words. For each string queries[i] in queries, find the number of strings in words such that f(queries[i]) < f(word) for each word in words.
Your task is to return an array answer such that answer[i] is the answer to the ith query.

/*Example*/

Given:
queries = ["bbb", "cc"]
words = ["a", "aa", "aaa", "aaaa"]
Expected output: [1, 2]
Explanation: For the first query only f("bbb") < f("aaaa"). For the second query both f("cc") < f("aaa") and f("cc") < f("aaaa").

Solution:

The first step will be finding the frequencies for each string in queries and words. We will implement the function findFreqSmallestChar corresponding to f(str), that is, findFreqSmallestChar will find the frequency of the lexicographically smallest character in the given string. We will collect these frequencies in queriesFreqs and wordsFreqs for queries and words respectively.
Then we will sort the wordsFreqs array.

Now, for each query = queries[i], we will count the required number of words. There will be queryFreq = queriesFreqs[i] corresponding to query. The answer to the query will be equal to the count of frequencies in wordsFreqs which are greater than queryFreq. Let the answer to the query is queryAnswer. To find queryAnswer, we will do the binary search over wordsFreqs and find the smallest index idx such that queryFreq > wordsFreqs[idx]. Then, queryAnswer = wordsFreqs.length - idx. We will do this for each query.

/**
 * @param {string[]} queries
 * @param {string[]} words
 * @return {number[]}
 */
function numSmallerByFrequency(queries, words) {
    const queriesFreqs = queries.map(findFreqSmallestChar)
    const wordsFreqs = words.map(findFreqSmallestChar)
    
    wordsFreqs.sort((a, b) => a - b)
    
    return queriesFreqs.map(queryFreq => countWordsWithGreaterFreq(
        queryFreq,
        wordsFreqs
    ))
}

function findFreqSmallestChar(str) {
    let freqSmallestChar = 0
    let smallestChar = str[0]
    
    for (const char of str) {
        if (char > smallestChar) continue
        if (char === smallestChar) freqSmallestChar++
        else {
            smallestChar = char
            freqSmallestChar = 1
        }
    }
    
    return freqSmallestChar
}

function countWordsWithGreaterFreq(queryFreq, wordsFreqs) {
    let left = 0
    let right = wordsFreqs.length
    
    while(left < right) {
        let mid = (left + right) / 2
        mid = Math.floor(mid)
        
        if (wordsFreqs[mid] > queryFreq) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    const queryAnswer = wordsFreqs.length - left
    return queryAnswer
}

n = length of queries array
m = length of words array
Time complexity- O((m + n) logm)
Space complexity- O(m + n)

Written by S. Kumar on May 22nd, 2021

8. Can you find the right interval indices for each interval?

This interview question shows the developer's ability to work with JavaScript sorting and intervals.

You are given an array intervals, where intervals[i] = [starti, endi] and each starti is unique.
The right interval for an interval i is an interval j such that startj >= endi and startj is minimized. Your task is to return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

/*Example*/

Given intervals = [[3, 4], [2, 3], [1, 2]]
Expected output:- [-1, 0, 1]
Explanation:- There is no right interval for [3, 4].
The right interval for [2, 3] is [3, 4].
The right interval for [1, 2] is [2, 3].

Solution:

We will sort the interval array according to the start of the intervals. Then, we do a binary search over the sorted intervals for each interval to find the corresponding right interval.
Since after sorting the original index for a particular interval is lost, we store the original indices corresponding to all the intervals in the map startIdxMap. The keys of startIdxMap will be the start of intervals and the values will be corresponding original indices.
When we find the right interval in the sorted intervals, we find the corresponding original indices for both the current interval and the right interval in intervalOriginalIdx and rightIntervalOriginalIdx respectively. We put the answers at the correct places in the answer array and return the array.

/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
function findRightInterval(intervals) {
    const startIdxMap = new Map()
    
    intervals.forEach((interval, idx) => {
        const start = interval[0]
        startIdxMap.set(start, idx)
    })
    
    intervals.sort((interval1, interval2) => {
        return interval1[0] - interval2[0]
    })
    
    const answer = new Array(intervals.length)
    
    for (let i = 0; i < intervals.length; i++) {
        const intervalEnd = intervals[i][1]
    
        let left = 0
        let right = intervals.length
        let rightStart = -Infinity
    
        while(left < right) {
            let mid = (left + right) / 2
            mid = Math.floor(mid)

            if (intervals[mid][0] >= intervalEnd) {
                right = mid
                rightStart = intervals[mid][0]
            } else {
                left = mid + 1
            }
        }
        
        const intervalOriginalIdx = startIdxMap.get(intervals[i][0])

        if (rightStart === -Infinity) {
            // no right interval
            answer[intervalOriginalIdx] = -1
        } else {
            const rightIntervalOriginalIdx =
                startIdxMap.get(rightStart)
            answer[intervalOriginalIdx] = rightIntervalOriginalIdx            
        }
    }
    
    return answer
}

n = number of intervals
Time complexity- O(n logn)
Space complexity- O(n)

Written by S. Kumar on May 22nd, 2021

9. What is the magnetic force between two balls?

This question concentrates on JavaScript sorting and binary search.

You are on a planet Earth in a different universe. You discovered a different kind of magnetic force between some special balls when placed in special baskets. If two balls are placed in two buckets separated by distance d, then the magnetic force between the balls is equal to d units.
You are given the positions of n baskets in array baskets. You also have m balls. Your task is to place these m balls in these buckets such that the minimum magnetic force between any two balls is maximum.

/*Example*/

Given baskets = [1, 2, 3, 4, 7]		m = 3
Expected output:- 3
Explanation:- After placing balls in baskets 1, 4, 7, the magnetic force between these balls 3, 3, 6. So the minimum magnetic force between any two balls is 3. We can not place balls in any other way such that the minimum magnetic force is larger.

Solution:

First of all, we sort the positions of the given baskets. Then we will do the binary search over these positions.
Letâ€™s say countBallsWithMinForce is a function that counts the number of balls that can be placed in the given baskets such that the minimum magnetic force between those balls is at least minimumForce. We seek to find the largest minimumForce such that,
countBallsWithMinForce(minimumForce) == m

That is, we need to find such a minimum magnetic force so that the number of balls that can be placed with that force is exactly equal to m.
â— If the countBallsWithMinForce(minimumForce) > m , we have too many balls placed, so minimumForce is too small.
â— If the countBallsWithMinForce(minimumForce) < m , we don't have enough balls placed, so minimumForce is too large.

Because countBallsWithMinForce(minimumForce) is monotonically decreasing with respect to minimumForce, we can use binary search to find the optimal minimumForce.

/**
 * @param {number[]} baskets
 * @param {number} m
 * @return {number}
 */
function maxDistance(baskets, m) {
    const n = baskets.length
    baskets.sort((a, b) => a - b)
    
    let left = 1
    let right = baskets[n - 1] - baskets[0] + 1
    
    while(left < right) {
        let mid = (left + right) / 2
        mid = Math.floor(mid)
        
        const ballsCountWithForceMid = countBallsWithMinForce(
            mid,
            baskets,
        )
        
        if (ballsCountWithForceMid < m) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return left - 1
}

function countBallsWithMinForce(minimumForce, baskets) {
    let count = 1
    let currPosition = baskets[0]
    
    for (let i = 1; i < baskets.length; i++) {
        const force = baskets[i] - currPosition
        if (force < minimumForce) continue
        
        count++
        currPosition = baskets[i]
    }
    
    return count
}

n = number of baskets
Time complexity- O(n (logn + log(max position))
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

10. How do you search in a rotated sorted array?

This question focuses on JavaScript arrays and sorting.

There was a sorted integer array nums of length n containing distinct numbers. nums is rotated by a pivot index k to form rotatedNums array, that is, rotatedNums = [nums[k], nums[k + 1], ..., nums[n - 1], nums[0], nums[1], ..., nums[k - 1]]. For example, if nums = [0, 1, 2, 3, 4, 5, 6, 7] and k = 3, then rotatedNums = [3, 4, 5, 6, 7, 0, 1, 2].

You are given rotatedNums and an integer target. Your task is to search the index of the target in rotatedNums. If it does not exist, return -1.

/*Example*/

Given rotatedNums = [4, 5, 6, 7, 0, 1, 2]	target = 0
Expected output:- 4

Solution:

The given array rotatedNums is not fully sorted. So we can not do a binary search directly.
Consider rotatedNums = [3, 4, 5, 6, 7, 0, 1, 2].

â— If we wish to search 1, we can adjust the array to [-Infinity, -Infinity, -Infinity, -Infinity, -Infinity, 0, 1, 2] and then we can perform binary search easily.
â— If we wish to search 5, we can adjust the array to [3, 4, 5, 6, 7, Infinity, Infinity, Infinity], and then we can perform a binary search easily.

The catch is that we won't actually adjust the array. We will calculate this on the fly. Letâ€™s call the rotated subarray [3, 4, 5, 6, 7] as the left side and [0, 1, 2] as the right side. A number is on the left side if num >= rotatedNums[0], otherwise it is on the right side.

If the target and rotatedNums[mid] are on the same side, we just take num = rotatedNums[mid]. If they are not on the same side, we take num to be equal to either Infinity or -Infinity. If the target is on the left side, num will be Infinity, otherwise, it will be -Infinity.

/**
 * @param {number[]} rotatedNums
 * @param {number} target
 * @return {number}
 */
function search(rotatedNums, target) {
    let left = 0
    let right = rotatedNums.length - 1
    const isTargetOnLeftSide = target >= rotatedNums[0]
    
    while(left < right) {
        let mid = (left + right) / 2
        mid = Math.floor(mid)
        
        let num = rotatedNums[mid]
        const isNumOnLeftSide = num >= rotatedNums[0]
        
        if (isTargetOnLeftSide !== isNumOnLeftSide) {
            num = isTargetOnLeftSide ? Infinity : -Infinity
        }
        
        if (num >= target) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return rotatedNums[left] === target ? left : -1
}

n = number of baskets
Time complexity- O(logn)
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

11. Find the minimum radius of the heaters where all houses can be warmed.

This question shows the developer's ability to work with JavaScript binary search.

There are some houses and heaters placed on a horizontal line. You are given the positions of the houses and heaters in array houses and heaters. All the heaters have the same radius up to which they can heat. A house can be warmed if it is within the radius range of at least one heater. Your task is to find the minimum radius of the heaters such that all houses can be warmed.

/*Example*/

Given	houses = [1, 2, 3, 6]		heaters = [1, 4]
Expected output:- 2
Explanation:- The heater at position 1 can warm houses at position 1 and 2 requiring radius of 1. The heater at position 4 can warm houses at position 3 and 6 requiring a radius of 2. Thus all the houses are warmed. If we increase the radius, all the houses will still be warmed. But if we decrease the radius of the second heater to 1, the house at position 6 can not be warmed. So the minimum radius is 2.

Solution:

First of all, we will sort the heaters array. Then, for each house, we will find the nearest heater so that it can be warmed.

To find the nearest heater for a house with position housePos, we will binary search over heaters array to find the nearest heater on the right side to housePos. We use the findRightHeater function for this. It will return the index of the right heater. If the right heater does not exist (it means there is no heater on the right side of housePos), it returns -1.

When we have the index of the right heater (in rightHeaterIdx), we find the positions of the right and left heaters. If any heater does not exist, we use Infinity to represent it at an infinity position and canâ€™t warm the house. These positions are stored in rightHeaterPos and leftHeaterPos. Then we find the distances of these heaters from the house and find the distance of the nearest heater in nearestHeaterDist. Then we update the result accordingly. And return it at the end.

/**
 * @param {number[]} houses
 * @param {number[]} heaters
 * @return {number}
 */
function findRadius(houses, heaters) {
    heaters.sort((a, b) => a - b)
    
    let result = -Infinity
    
    for (const housePos of houses) {
        const rightHeaterIdx = findRightHeater(housePos, heaters)
        
        const rightHeaterPos = findRightHeaterPos(
            rightHeaterIdx,
            heaters
        )
        const leftHeaterPos = findLeftHeaterPos(
            rightHeaterIdx,
            heaters
        )
        
        const rightHeaterDist = Math.abs(housePos - rightHeaterPos)
        const leftHeaterDist = Math.abs(housePos - leftHeaterPos)
        
        const nearestHeaterDist = Math.min(
            rightHeaterDist,
            leftHeaterDist
        )
        result = Math.max(result, nearestHeaterDist)
    }
    
    return result
}

function findRightHeaterPos(rightHeaterIdx, heaters) {
    if (rightHeaterIdx === -1) return Infinity
    return heaters[rightHeaterIdx]
}

function findLeftHeaterPos(rightHeaterIdx, heaters) {
    if (rightHeaterIdx === 0) return Infinity
    if (rightHeaterIdx === -1) return heaters[heaters.length - 1]
    return heaters[rightHeaterIdx - 1]
}

function findRightHeater(housePos, heaters) {
    let left = 0
    let right = heaters.length
    
    while (left < right) {
        let mid = (left + right) / 2
        mid = Math.floor(mid)
        
        if (heaters[mid] >= housePos) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    if (left === heaters.length) return -1
    return left
}

n = number of houses
m = number of heaters
Time complexity- O((m + n) logm)
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

12. Can you find the H-index?

This question shows the developer's ability to work with JavaScript binary search.

A scientist has an index h if h of their n papers have at least h citations each, and the other n âˆ’ h papers have no more than h citations each.
You are given n citations of a scientist in array citations in sorted order. Your task is to find the h-index of the scientist.

/*Example*/

Given:- citations = [0, 1, 4, 5, 6]
Expected output:- 3
Explanation:- The scientist has published 5 papers and they have received 0, 1, 4, 5 and 6 citations respectively. Out of these papers, 3 papers have received at least 3 citations and then the rest two papers have less than 3 citations.

Solution:

The task is very simple with binary search. For a given index idx, the number of citations after this index (including itself) is equal to citations.length - idx. We will find first such index idx such that citations[idx] >= citations.length - idx, that is, we will find a first paper which has citations (citations[idx]) greater than or equal to the number of papers which has equal to the greater number of citations (the required condition for h-index).

/**
 * @param {number[]} citations
 * @return {number}
 */
function hIndex(citations) {
    const citationsCount = citations.length
    let left = 0
    let right = citations.length
    
    while(left < right) {
        let mid = (left + right) / 2
        mid = Math.floor(mid)
        
        if (citations[mid] >= citationsCount - mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return citationsCount - left
}

n = number of citations
Time complexity- O(logn)
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

13. What is the minimum speed to arrive on time?

This question shows the developer's knowledge of JavaScript binary search.

You work in an office. Your commute to the office from your home by train. You have to change many trains to go to the office. The distance covered by each train is given in array distances in km. After the first train, you take the second train, then the third, and so on. The last train reaches your office. Every train departs when the previous train has arrived. It departs only on integer hours. For example, if the first train arrives at 1.5 hours, you must wait for an additional 0.5 hours, and the second train will depart at 2 hours.

All the trains travel at the same speed. You are given a floating-point number of hours. Your task is to find the minimum speed of trains (integer in kilometers per hour) such that you can reach the office within hours. If you canâ€™t reach the office on time, return -1.

/*Example*/

Given:- distances = [1, 3, 2]		hour = 2.7
Expected output:- 3
Explanation:
â—	The first train takes 1/3 = 0.333 hours.
â—	We wait for 0.667 hours. Then the second train departs. It takes 3/3 = 1 hours. So total 2 hours.
â—	We are at integer hour. So the third train departs immediately. It takes 2/3 = 0.667 hours. Total time is 2.667 hours. 

Constraint
â—	hours will have at most two digits after the decimal point.
â—	the required speed wonâ€™t exceed 107.

Solution:

Since the required speed ranges between 1 and 107, we can do a binary search over this range. For each speed that we are checking, we will find the required to reach the office using the function findTimeRequired. If we can reach this speed (time <= hours), we narrow our search from the right end, otherwise we narrow our search from the left end.

/**
 * @param {number[]} distances
 * @param {number} hours
 * @return {number}
 */
function minSpeedOnTime(distances, hours) {
    let left = 1
    let right = Math.pow(10, 7) + 1
    let ans = -1
    
    while (left < right) {
        let mid = (left + right) / 2
        mid = Math.floor(mid)
        
        const time = findTimeRequired(distances, mid)
        
        if (time <= hours) {
            right = mid
            ans = mid
        } else {
            left = mid + 1
        }
    }
    
    return ans
}

function findTimeRequired(distances, speed) {
    const lastDistIdx = distances.length - 1
    let time = 0

    for (let i = 0; i < lastDistIdx; i++) {
        time += Math.ceil(distances[i] / speed)
    }

    time += distances[lastDistIdx] / speed    
    return time
}

n = number of trains
m = maximum speed of train i.e. 107
Time complexity- O(n logm)
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

14. Find the minimum in a rotated sorted array.

This question shows the developer's ability to work with JavaScript binary search and arrays.

There was a sorted integer array nums of length n containing distinct numbers. nums is rotated by a pivot index k to form rotatedNums array, that is, rotatedNums = [nums[k], nums[k + 1], ..., nums[n - 1], nums[0], nums[1], ..., nums[k - 1]]. For example, if nums = [0, 1, 2, 3, 4, 5, 6, 7] and k = 3, then rotatedNums = [3, 4, 5, 6, 7, 0, 1, 2].

You are given the array rotatedNums. Your task is to find the smallest number in the array.

/*Example*/

Given rotatedNums = [3, 4, 5, 1, 2]
Expected output:- 1

Given rotatedNums = [11, 13, 15, 17]
Expected output:- 11

Solution:

If the first number is smaller than the last number, it means it is the original array. So we return the first number directly.

Otherwise, we do a binary search over the array. Let's take the example of a rotated array [5, 6, 7, 8, 1, 2, 3, 4]. Letâ€™s call the parts [5, 6, 7, 8] and [1, 2, 3, 4] as the left and the right parts respectively. All the numbers in the right part are smaller than the first number in the array and smaller than or equal to the last number. We need to find the smallest number in the right part. We will do a binary search over the whole array. If the number at index mid is:

â— smaller than the first number in the array and smaller than or equal to the last number, it is in the right part. So we shrink the right pointer,
â— otherwise, it is the left part. So we shrink the left pointer.

After the loop ends, the left pointer will be the index of the minimum number.

/**
 * @param {number[]} rotatedNums
 * @return {number}
 */
function findMin(rotatedNums) {
    const lastNumIndex = rotatedNums.length - 1
    
    // rotated by k = 0 or n
    // which means it the original array
    if (rotatedNums[0] < rotatedNums[lastNumIndex]) {
        return rotatedNums[0]
    }

    let left = 0
    let right = lastNumIndex
    
    while (left < right) {
        let mid = (left + right) / 2
        mid = Math.floor(mid)
        
        const isSmallerThanFirst = nums[mid] < nums[0]
        const isSmallerThanLast = nums[mid] <= nums[lastNumIndex]
        
        if (isSmallerThanFirst && isSmallerThanLast) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return nums[left]
}

Time complexity- O(logn)
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

15. How do you find the K closest elements?

This question shows the developer's ability to work with JavaScript binary search and index.

You are given a sorted integer array arr. You are also given two integers k and num. Your task is to find k closest integers to num in arr. The closest integers to an integer num are num - 1 and num + 1; the next closest integers are num - 2 and num + 2 and so on. The result should be sorted in ascending order.

An integer a is closer to num than another integer b if:
â— either |num - a| < |num - b|,
â— or |num - a| == |num - b| and a < b

/*Example*/

Given	arr = [1, 2, 3, 4, 5]		k = 5		x = 3
Expected output:- [1, 2, 3, 4]

Constraint
â—	1 <= k <= arr.length

Solution:

Letâ€™s say we have an index idx. Consider two numbers arr[idx] and arr[idx + k]. Let us assume that the numbers arr[idx], arr[idx + 1], â€¦., arr[idx + k - 1] are the closest numbers to num. Now if these are the closest numbers to num, the average of the extreme numbers (arr[idx] and arr[idx + k - 1]) should be at least num and minimum possible. It means num should be at the middle element of the two extremes. If the average is less than num, it will be close to the larger extreme. If the average is much more than num, it will be close to the smaller extreme. Neither range will constitute the closest elements to num.
arr[idx] ..... num ..... arr[idx + k - 1]
(num is almost at middle)
arr[idx] .. num ... average ..... arr[idx + k - 1]
(average is much higher than num, so num is close to the left extreme)
arr[idx] ..... average ... num .. arr[idx + k - 1]
(average is lower num, so num is close to the right extreme)

More formally,
average = (arr[idx] + arr[idx + k - 1]) / 2
average >= num
and the average is the minimum possible.

As we increase idx, the average increases; as idx decreases the average decreases. So we can binary search over all the indexes (hence the array) to find the minimum idx such that The average is at least num.
After we find such an index (after the loop, left will be such index), we create a new array from arr from index left to left + k (exclusive). For this, we use the Array.prototype.slice method. The function creates a new array from the array between the passed indices. This takes two arguments:

1. startIndex (optional, defaults to 0):- This specifies the index from where to start copying.
2. endIndex (optional, defaults to the length of the array):- This specifies the index at where to end copying exclusively.

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} num
 * @return {number[]}
 */
function findClosestElements(arr, k, num) {
    let left = 0
    let right = arr.length - k
    
    while (left < right) {
        let mid = (left + right) / 2
        mid = Math.floor(mid)
        
        if (2 * num <= arr[mid] + arr[mid + k]) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    
    return arr.slice(left, left + k)
}

Time complexity- O(logn)
Space complexity- O(1)

Written by S. Kumar on May 22nd, 2021

16. What is the random pick with weight?

This question shows the developer's ability to work with JavaScript binary search and weights.

You are given an array of positive integer weights. You need to initialize a data structure with given weights. The method pickIndex randomly returns an index between 0 and weights.length - 1. The probability of indices is proportional to their weight in the weights array. That is, the probability for the index is equal to weights[i] / sum (weights).

For example, if weights = [2, 3]. When pickIndex is called, the probability of getting index 0 is 2 / (2 + 3) = 40% while the probability of getting index 1 is 3 / (2 + 3) = 60%.
Your task is to provide an implementation for this DS such that pickIndex has minimum time complexity.

class Solution {
    /**
     * @param {number[]} weights
     */
    constructor(weights) {
    }

    /**
     * @return {number}
     */
    pickIndex() {
    }
}

Solution:

We will find the accumulated weights (also known as prefix sums) in accWeights. For example if weights = [2, 5, 3, 4], then accWeights = [2, 7, 10, 14]. We will do this in the constructor function.
The max accumulated weight in the above array is 14 (that is the last element of the accWeights). In the pickIndex method, we will, first, find a random number between ranges [1, maxAccWeight]. Let this be randomAccWeight. Then using binary search, we will search the first such index in accWeights at which the accumulated weight is greater than or equal to randomAccWeight. That will be our required index.

How does this work?
Let weights = [2, 5, 3, 4], then accWeights = [2, 7, 10, 14]
Now, we get a random integer in the range [1, 14] with equal probability and is stored in randomAccWeight. There are 14 total possible values for randomAccWeight. Then we binary search this in the accumulated weights. So for the values of randomAccWeight, the searched indices will be:
randomAccWeight searched index probability of getting the index
in the range

----------------------------------------------------------------------
[1, 2] 0 2 / 14
[3, 7] 1 5 / 14
[8, 10] 2 3 / 14
[11, 14] 3 4 / 14

As it can be seen that, the probability of getting an index is proportional to the corresponding weight.

class Solution {
    /**
     * @param {number[]} weights
     */
    constructor(weights) {
        const accWeights = new Array(weights.length)
        accWeights[0] = weights[0]

        for (let i = 1; i < weights.length; i++) {
            accWeights[i] = accWeights[i - 1] + weights[i]
        }

        this.accWeights = accWeights
    }

    /**
     * @return {number}
     */
    pickIndex() {
        const {
            accWeights
        } = this
        let left = 0
        let right = accWeights.length - 1
        const maxAccWeight = accWeights[right]
        const randomAccWeight = getRandomInt(1, maxAccWeight)

        while (left < right) {
            let mid = (left + right) / 2
            mid = Math.floor(mid)

            if (accWeights[mid] >= randomAccWeight) {
                right = mid
            } else {
                left = mid + 1
            }
        }

        return left
    }
}

function getRandomInt(min, max) {
    const random = Math.random() * (max - min + 1) + min
    return Math.floor(random)
}

Space complexity of the data structure- O(n)
Time complexity of constructor- O(n)
Space complexity of constructor- O(n)
Time complexity of pickIndex O(logn)
Space complexity of pickIndex O(1)

Written by S. Kumar on May 22nd, 2021