Kotlin Count number of occurrences (or frequency) in a sorted array

Count number of occurrences (or frequency) in a sorted array
Expected time complexity is O(Logn)

– Example:


Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 2
Output: 4 // x (or 2) occurs 4 times in arr[]

Solution -> Improved Binary Search
1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.
2) Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.
3) Return (j – i + 1);


import java.util.*

fun main() {
	var A = intArrayOf(1, 2, 2, 3, 4)
	println(solution(A, 2))
}

fun solution(A: IntArray, x: Int): Int {
	
	if (A.size == 0)
		return -1
	
	var leftOccur = binarySearchLeftMostOccurs(A, x, 0, A.size - 1)
	var rightOccur = leftOccur
	
	if (leftOccur == -1)
		return -1
	else {
		rightOccur = binarySearchRightMostOccurs(A, x, leftOccur, A.size - 1)
	} 
	
	return rightOccur - leftOccur + 1
}

fun binarySearchLeftMostOccurs(A: IntArray, x: Int, leftmost: Int, rightmost: Int): Int {

	if(leftmost == rightmost) {
		if (A[leftmost] == x) {
			return leftmost
		}
		
		return -1
	}
	
	var pivot = (leftmost + rightmost) / 2
	
	if(A[pivot] == x && ((pivot == leftmost) || (A[pivot - 1] < A[pivot]))) {
		return pivot
	}
	
	if(A[pivot] >= x){
		return binarySearchLeftMostOccurs(A, x, leftmost, pivot)
	}else {
		return binarySearchLeftMostOccurs(A, x, pivot + 1, rightmost)
	}
}

fun binarySearchRightMostOccurs(A: IntArray, x: Int, leftmost: Int, rightmost: Int): Int {
	if(leftmost == rightmost) {
		if (A[rightmost] == x) {
			return rightmost
		}
		
		return -1
	}
	
	var pivot = (leftmost + rightmost) / 2
	
	if(A[pivot] == x && ((pivot == rightmost) || (A[pivot] < A[pivot + 1]))) {
		return pivot
	}
	
	if(A[pivot] <= x){
		return binarySearchRightMostOccurs(A, x, pivot + 1, rightmost)
	}else {
		return binarySearchRightMostOccurs(A, x, leftmost, pivot)
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *