Sunday, 23 May 2021

Java Program To Search For A Range In Sorted Array

Problem:
We need to find first and last positions of an element in a sorted array.  In case element is not present, we need to return [-1, -1].

Input:
    A = [5, 7, 7, 8, 8, 10]
    B = 8
Output:
    [3, 4]
This is an interview question which is asked in companies like Google & Microsoft. You can find the question in popular sites like InterviewBit & LeetCode.

We can use modified version of binary search to find the range of the element. For leftmost element, we should move left side even when we find B & keep on updating the leftmost position. Same goes for rightmost element. In that case we need to keep on moving towards right side even when we encounter B. 

We are doing two binary searches, so overall time complexity would be O(log n).

Here is the fully working Java solution of the problem.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public ArrayList<Integer> searchRange(final List<Integer> A, int B) {
        int leftPos = findLeftMost(A, B);
        int rightPos = findRightMost(A, B);
        ArrayList<Integer> result = new ArrayList<Integer>();
        result.add(leftPos);
        result.add(rightPos);
        return result;
    }
    
    private int findLeftMost(final List<Integer> A, int B){
        int pos = -1;
        int lowerBound = 0;
        int upperBound = A.size() - 1;
        while(upperBound >= lowerBound){
            int mid = lowerBound + ((upperBound - lowerBound)/ 2);
            if(B <= A.get(mid)){
                if(A.get(mid) == B){
                    pos = mid;
                }
                upperBound = mid - 1;
            } else {
                lowerBound = mid + 1;
            }
        }
        return pos;
    }
    
    private int findRightMost(final List<Integer> A, int B){
        int pos = -1;
        int lowerBound = 0;
        int upperBound = A.size() - 1;
        while(upperBound >= lowerBound){
            int mid = lowerBound + ((upperBound - lowerBound) / 2);
            if(B >= A.get(mid)){
                if(A.get(mid) == B){
                    pos = mid;
                }
                lowerBound = mid + 1;
            } else {
                upperBound = mid - 1;
            }
        }
        return pos;
    }
}

No comments:

Post a Comment

Java Program To Solve Maximum Size Rectangle In Binary Matrix

Given a binary matrix, find max rectangle with all 1's. A : [ 1 1 1 0 0 1 1 0 1 1 1 0 ] Output : 6 Dynamic programmi...