Learn-dsa..in 30 days!



























CC-16 : Find numbers smaller than current.

Description:

Given an input array, sort the elements of array and create a new array and for each number at a particular index of sorted array, in new array put count of numbers lesser than number in sorted array.

Test cases and expected outputs:

Input Parameters Expected outputs
Array 1:
33, 3, 4, 97, 62, 122, 124, 20, 1, 		Sorted Array:
1, 3, 4, 20, 33, 62, 97, 122, 124,

Nums smaller than current num stored at same index:
0, 1, 2, 3, 4, 5, 6, 7, 8,

Pseudocode:

findNumbersSmallerThanCurrent(nums[]):

Set nums=quicksort(nums).
Initialize integer array variable named numsLesser and sets its length to nums.length.
Iterate through nums using for loop with idx as iteration variable and values of idx ranging from 0 to nums.length-1:
Find the index of nums[idx] in sorted array. Since array is sorted, the index at which nums[idx] is found is the number of elements lesser than nums[idx] in the sorted array.
Set numsLesser[idx] to index at which nums[idx] was found.
Return numsLesser.

QuickSort(nums[], startIdx, endIdx):

Integer array named nums, start index startIdx and end index endIdx of nums are received as input parameters.
If (startIdx < endIdx) then execute following steps:
Initialize and integer variable pivot with value nums[endIdx]. We will use this variable to partition the elements into two partitions.
Initialize and integer variable iidx with value startIdx-1. We will use this variable to track and swap elements less than pivot to partition containing elemnts lesser than the pivot.
Iterate through using for loop with jidx as iteration variable and values of iidx ranging from startIdx to endIdx-1:
If nums[jidx]<=pivot then:
Increment iidx by 1.
Swap elements at position iidx and jidx.
Swap elements at index iidx+1 and endIdx.
Set integer variable partitionIdx to iidx+1.
Call method quicksort(nums, startIdx, partitionIdx-1) to sort the partition with lesser elements than pivot element.
Call method quicksort(nums, partitionIdx+1, endIdx,) to sort the partition with greater elements than pivot element.
The element of nums array have been sorted now using Quick Sort, so return nums array from the method.

binarySearch(nums[], toSearch):

Integer array named nums and integer named toSearch to be searched are received as input parameters.
Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.
Set integer variable lastIdx to nums.length-1, we will use this variable to check the last index of partition in which are searching for required integer.
While (firstIdx <= lastIdx) do the following steps:
Set integer variable midCount to (lastIdx-firstIdx)/2.
Set integer variable midIdx to (firstIdx+midCount)to get mid index of current partition. We will use midIdx to partition the array into 2 parts.
If (nums[midIdx]==toSearch) return midIdx; this means have found the required element.
Else if nums[midIdx > toSearch then:
Set lastIdx=(midIdx-1) as we need to search in lower partition now.
Else:
Set firstIdx=midIdx+1, as we need to search in the higher partition now.
If toSearch is not found in code above return -1, as the required element does not exist within the input array.

Code:

public int[] findNumbersSmallerThanCurrent(int[] nums) {
	nums=quickSort(nums, 0, nums.length-1);
	int[] numsLesser=new int[nums.length];
	for (int idx=0; idx < nums.length;idx++){
		numsLesser[idx]=binarySearch(nums, nums[idx]);
	}
	return numsLesser;
}

public int[] quickSort(int[] nums,int startIdx, int endIdx) {
	if(startIdx < endIdx) {
		int pivot=nums[endIdx];
		int iidx=startIdx-1;
		for (int jidx=startIdx; jidx < endIdx;jidx++) {
			if (nums[jidx] <= pivot) {
				iidx++;		
				int swap=nums[iidx];
				nums[iidx]=nums[jidx];
				nums[jidx]=swap;
			}
		}
		int swap=nums[iidx+1];
		nums[iidx+1]=nums[endIdx];
		nums[endIdx]=swap;
		
		int partitionIdx=iidx+1;
		quickSort(nums, startIdx, partitionIdx-1);
		quickSort(nums, partitionIdx+1,endIdx);
	}
	return nums;
}

public int binarySearch(int[] nums, int toSearch){
	int firstIdx=0;
	int lastIdx=nums.length-1;
	while (firstIdx <= lastIdx) {
		int midCount=(lastIdx-firstIdx)/2;
		int midIdx=firstIdx+midCount;
		if (nums[midIdx]==toSearch) {
			return midIdx;
		} else { if (nums[midIdx]> toSearch) {
			lastIdx=midIdx-1;
		}else {
			firstIdx=midIdx+1;
		}
		}		
	}	
	return -1;
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us