Left most and right most index in Java
Given a sorted array or a list of elements and a target value, the task is to find the leftmost and rightmost indices of that value within the collection. If the value is not present, return appropriate indicators (like -1) to signify its absence.
Example 1
Input: N = 8, arr[] = {2, 4, 4, 4, 4, 4, 4, 6}, target = 4
Output: 1 6
Explanation: The first occurrence of 4 is at index 1, and the last occurrence is at index 6.
Example 2
Input: N = 5, arr[] = {1, 2, 3, 4, 5}, target = 6
Output: -1 -1
Explanation: The element 6 is not present in the array, so both the leftmost and rightmost indices are -1.
Example 3
Input: N = 9, arr[] = {1, 3, 5, 5, 5, 5, 67, 123, 125}, target = 5
Output: 2 5
Explanation: Index of first occurrence of 5 is 2 and index of last occurrence of 5 is 5.
Approach 1: Using Linear Search
Linear search is a simple searching algorithm that sequentially checks each element in a collection until a match is found or the entire collection has been traversed. It is straightforward and easy to implement but not very efficient for large datasets compared to more advanced algorithms like binary search or hash tables.
Algorithm
Step 1: Start traversing the array from the leftmost element.
Step 2: Compare each element of the array with the target value.
Step 3: If the element matches the target, return its index.
Step 4: If no match is found after traversing the entire array, return -1.
Step 5: Start traversing the array from the rightmost element.
Step 6: Compare each element of the array with the target value.
Step 7: If the element matches the target, return its index.
Step 8: If no match is found after traversing the entire array, return -1.
FileName: LinearSearchLeftRight.java
public class LinearSearchLeftRight { // Linear search for leftmost index public static int linearSearchLeft(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) { return i; // Return the index if target found } } return -1; // Return -1 if target not found } // Linear search for rightmost index public static int linearSearchRight(int[] arr, int target) { for (int i = arr.length - 1; i >= 0; i--) { if (arr[i] == target) { return i; // Return the index if target found } } return -1; // Return -1 if target not found } public static void main(String[] args) { int[] arr = {1, 2, 2, 3, 3, 3, 4, 5}; int target = 3; // Linear search for leftmost index int leftLinear = linearSearchLeft(arr, target); System.out.println("Leftmost index (Linear search): " + leftLinear); // Linear search for rightmost index int rightLinear = linearSearchRight(arr, target); System.out.println("Rightmost index (Linear search): " + rightLinear); } }
Output
Leftmost index (Linear search): 3 Rightmost index (Linear search): 5
Time Complexity: The time complexity of linear search is O(n), where n is the number of elements in the array. This is because the algorithm may need to traverse the entire array to find the target element.
Space Complexity: The space complexity of linear search is O(1) because it only requires a constant amount of extra space regardless of the size of the input array. This is because the algorithm operates directly on the input array without requiring additional data structures.
Approach 2: Using Binary Search
Binary search is a search algorithm that finds the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half until the target value is found or the interval is empty.
Algorithm
Step 1: Start with two pointers, left and right, representing the left and right boundaries of the search space.
Step 2: Initialize result to -1 to indicate that the target is not found.
Step 3: In each iteration, calculate the middle index (mid) of the current search space.
Step 4: If the element at mid is equal to the target, update result to mid and continue searching on the left side by moving right to mid - 1.
Step 5: If the element at mid is less than the target, update left to mid + 1.
Step 6: If the element at mid is greater than the target, update right to mid - 1.
Step 7: Continue the process until left is greater than right.
Step 8: Follow the same steps as the leftmost index search, but update result and the search boundaries differently:
Step 8.1: If the element at mid is equal to the target, update result to mid and continue searching on the right side by moving left to mid + 1.
FileName: BinarySearchLeftRight.java
public class BinarySearchLeftRight { // Binary search for leftmost index public static int binarySearchLeft(int[] arr, int target) { int left = 0; // Initialize left pointer int right = arr.length - 1; // Initialize right pointer int result = -1; // Initialize result to -1 (not found) // Binary search loop while (left <= right) { int mid = left + (right - left) / 2; // Calculate middle index // If target found, update result and continue searching on the left side if (arr[mid] == target) { result = mid; right = mid - 1; // Move right pointer to mid - 1 } else if (arr[mid] < target) { // If target is in the right half left = mid + 1; // Move left pointer to mid + 1 } else { // If target is in the left half right = mid - 1; // Move right pointer to mid - 1 } } return result; // Return leftmost index of target } // Binary search for rightmost index public static int binarySearchRight(int[] arr, int target) { int left = 0; // Initialize left pointer int right = arr.length - 1; // Initialize right pointer int result = -1; // Initialize result to -1 (not found) // Binary search loop while (left <= right) { int mid = left + (right - left) / 2; // Calculate middle index // If target found, update result and continue searching on the right side if (arr[mid] == target) { result = mid; left = mid + 1; // Move left pointer to mid + 1 } else if (arr[mid] < target) { // If target is in the right half left = mid + 1; // Move left pointer to mid + 1 } else { // If target is in the left half right = mid - 1; // Move right pointer to mid - 1 } } return result; // Return rightmost index of target } public static void main(String[] args) { int[] arr = {1, 2, 2, 3, 3, 3, 4, 5}; int target = 3; // Binary search for leftmost index int leftBinary = binarySearchLeft(arr, target); System.out.println("Leftmost index (Binary search): " + leftBinary); // Binary search for rightmost index int rightBinary = binarySearchRight(arr, target); System.out.println("Rightmost index (Binary search): " + rightBinary); } }
Output
Leftmost index (Binary search): 3 Rightmost index (Binary search): 5
Time Complexity: The time complexity of binary search is O(log n), where n is the number of elements in the array. This is because the search space is halved in each iteration.
Space Complexity: The space complexity of binary search is O(1) because it only requires a constant amount of extra space regardless of the size of the input array.
Approach 3: Using Java Streams
Java streams used to find the indices of the leftmost and rightmost occurrences of a target value in a sorted array. We can achieve this by streaming over the indices of the array and filtering them based on the target value. Then we can find the minimum and maximum indices of the filtered elements to get the leftmost and rightmost occurrences.
Algorithm
Step 1: We create an IntStream from 0 to arr.length - 1.
Step 2: Using the filter operation, we retain only the indices where the element at that index equals the target value.
Step 3: We use findFirst() to get the index of the first occurrence of the target value, which represents the leftmost index.
Step 4: Similar to the leftmost index, we create an IntStream from 0 to arr.length - 1.
Step 5: Using the filter operation, we retain only the indices where the element at that index equals the target value.
Step 6: We use reduce to reduce the stream to the last occurrence of the target value, thus finding the rightmost index.
FileName: StreamLeftRight.java
import java.util.stream.IntStream; public class StreamLeftRight { // Java stream to find leftmost index public static int streamLeft(int[] arr, int target) { return IntStream.range(0, arr.length) // Create a stream of integers from 0 to arr.length - 1 .filter(i -> arr[i] == target) // Filter elements where arr[i] equals the target value .findFirst() // Find the first occurrence of the target value .orElse(-1); // Return -1 if not found } // Java stream to find rightmost index public static int streamRight(int[] arr, int target) { return IntStream.range(0, arr.length) // Create a stream of integers from 0 to arr.length - 1 .filter(i -> arr[i] == target) // Filter elements where arr[i] equals the target value .reduce((first, second) -> second) // Reduce the stream to the rightmost index .orElse(-1); // Return -1 if not found } public static void main(String[] args) { int[] arr = {1, 2, 2, 3, 3, 3, 4, 5}; // Sample array int target = 3; // Target value to find // Java stream to find leftmost index int leftStream = streamLeft(arr, target); // Call streamLeft method to find leftmost index System.out.println("Leftmost index (Stream): " + leftStream); // Print the leftmost index // Java stream to find rightmost index int rightStream = streamRight(arr, target); // Call streamRight method to find rightmost index System.out.println("Rightmost index (Stream): " + rightStream); // Print the rightmost index } }
Output
Leftmost index (Stream): 3 Rightmost index (Stream): 5
Time Complexity: The time complexity of an algorithm is O(n), where n is length of the array. This is because both the leftmost and rightmost operations iterate through the array once using a stream.
Space Complexity: The space complexity of an algorithm is O(1) because we're not creating any additional data structures that scale with the size of the input array. Java streams handle elements in a lazy and efficient manner, resulting in minimal additional space requirements.
Approach 4: Using Two Pointers
The Two Pointer approach is a technique used to solve problems efficiently by using two pointers to traverse through a data structure, usually an array or a linked list.
Algorithm
Step 1: Initialize two pointers, left and right, pointing to the start and end of the array respectively.
Step 2: Initialize left to 0 and right to arr.length - 1.
Step 3: While left is less than or equal to right:
Step 3.1: If the element at arr[left] is equal to the target, return left.
Step 3.2: Otherwise, increment left to move it to the right.
Step 4: If the target is not found, return -1.
Step 5: While left is less than or equal to right:
Step 5.1: If the element at arr[right] is equal to the target, return right.
Step 5.2: Otherwise, decrement right to move it to the left.
Step 6: If the target is not found, return -1.
FileName: TwoPointerleftright.java
public class TwoPointerleftright { // Method to find leftmost index using two pointers public static int findLeft(int[] arr, int target) { int left = 0; // Initialize left pointer int right = arr.length - 1; // Initialize right pointer while (left <= right) { // Iterate until left pointer exceeds right pointer if (arr[left] == target) { // If target found at left pointer, return left index return left; } left++; // Move left pointer to the right } return -1; // If target not found, return -1 } // Method to find rightmost index using two pointers public static int findRight(int[] arr, int target) { int left = 0; // Initialize left pointer int right = arr.length - 1; // Initialize right pointer while (left <= right) { // Iterate until left pointer exceeds right pointer if (arr[right] == target) { // If target found at right pointer, return right index return right; } right--; // Move right pointer to the left } return -1; // If target not found, return -1 } public static void main(String[] args) { int[] arr = {1, 2, 2, 3, 3, 3, 4, 5}; // Sample array int target = 3; // Target value to find // Find leftmost index using two pointers int leftIndex = findLeft(arr, target); System.out.println("Leftmost index (Two Pointer): " + leftIndex); // Find rightmost index using two pointers int rightIndex = findRight (arr, target); System.out.println("Rightmost index (Two Pointer): " + rightIndex); } }
Output
Leftmost index (Two Pointer): 3 Rightmost index (Two Pointer): 5
Time Complexity: The time complexity of an algorithm is O(n), where n is the number of elements in the array. This is because both findLeft and findRight methods perform a linear scan through the array.
Space Complexity: The space complexity of an algorithm is O(1). This is because the algorithm uses only a constant amount of extra space for the pointers.