Binary Search

Question 1

153. Find Minimum in Rotated Sorted Array
     Solved
     Medium
     Topics
     Companies
     Hint
     Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Answer 1

class Solution {
public int findMin(int[] nums) {

    if(nums[nums.length-1]>nums[0]){
        return nums[0];
    }

    if(nums.length ==1){
        return nums[0];
    }

    int left = 0;
    int right = nums.length-1;

    while(left<=right){
        int mid = (left+right)/2;

        if(nums[mid]>nums[mid+1]){
            return nums[mid+1];
        }
         if(nums[mid-1]>nums[mid]){
            return nums[mid];
        }
        if (nums[mid] > nums[0]) {
            left = mid + 1;
        } 
        else {
            // if nums[0] is greater than the mid value then this means the smallest value
            // is somewhere to
            // the left
            right = mid - 1;
        }
    }
    return -1;
} }

Question 2

1351. Count Negative Numbers in a Sorted Matrix

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.
Example 2:

Input: grid = [[3,2],[1,0]]
Output: 0

Answer 2

class Solution {
public int countNegatives(int[][] grid) {
int count = 0;

    int row = 0;
    int col = grid[0].length - 1;

    while(row<=grid.length-1 && col>=0){
        if(grid[row][col]<0){
            count = count + grid.length-row;
            col--;
        }
        else{
            row++;
        }
    }
    return count;
} }

Question 3

2594. Minimum Time to Repair Cars
      Medium
      Topics
      Hint
      You are given an integer array ranks representing the ranks of some mechanics. ranksi is the rank of the ith mechanic. A mechanic with a rank r can repair n cars in r * n2 minutes.

You are also given an integer cars representing the total number of cars waiting in the garage to be repaired.

Return the minimum time taken to repair all the cars.

Note: All the mechanics can repair the cars simultaneously.

Example 1:

Input: ranks = [4,2,3,1], cars = 10
Output: 16
Explanation:
- The first mechanic will repair two cars. The time required is 4 * 2 * 2 = 16 minutes.
- The second mechanic will repair two cars. The time required is 2 * 2 * 2 = 8 minutes.
- The third mechanic will repair two cars. The time required is 3 * 2 * 2 = 12 minutes.
- The fourth mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes.
It can be proved that the cars cannot be repaired in less than 16 minutes.​​​​​

Answer 3

class Solution {
public long repairCars(int[] ranks, int cars) {

    Arrays.sort(ranks);
    long left = 1;
    long right = ranks[0] * cars * cars;// 100
    while (left < right) {
        long mid = (left + right) / 2;
        boolean isAbleToRepair = isAbleToRepair(ranks, cars, mid);

        if (isAbleToRepair == true) {
            right = mid;
        }

        else {
            left = mid + 1;
        }
    }
    return left;
}

public boolean isAbleToRepair(int[] ranks, int cars, long minutes) {
    long numOfCar = 0;

    for (int i = 0; i < ranks.length; i++) {
        numOfCar = numOfCar + (long)Math.sqrt(minutes / ranks[i]);
    }
   
    if (numOfCar >= cars) {
        return true;
    }
    return false;
} }

Question 4

875. Koko Eating Bananas
     Attempted
     Medium
     Topics
     Companies
     Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4
Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Answer 4

class Solution {
public int minEatingSpeed(int[] piles, int h) {
Arrays.sort(piles);
int left = 1;
int right = piles[piles.length-1];
int mid=0;
while(left<right){
mid = (left+right)/2;
boolean canEat = canEat(mid, piles, h);
if(canEat==true){
right = mid;
}
else{
left=mid+1;
}
}
return left;
}

boolean canEat(int numbOfBanana, int []piles, int h){
    int count = 0;

    for(int i =0;i<piles.length;i++){
        int mod = piles[i]%numbOfBanana;
        int quotient = piles[i]/numbOfBanana;
        if(mod>0){
           count  = count+ 1+quotient;
        }
        else{
            count  = count+quotient;
        }

        
    }

    if(count<=h){
        return true;
    }
    return false;
} }