1.

Write a program to find the index of first occurrence and last occurrence of an element in the array in a single iteration.

Answer»
You cannot use extra space. The first index of occurrence and the last index of occurrence will be -1, if the element is not present inside the array.

We will keep three variables. The 2 variables (that are) firstIndex and lastIndex will be initialized to -1. The third will be a boolean type variable found which will be initially false. If the element is found, we will make it true, and store the current index in firstIndex and lastIndex variables. If the element is found further, only the lastIndex variable will change. The fact that the number has already been found in the array will be denoted by the found boolean variable.

Java Program to find the First and Last Occurrence of an element in the Array

import java.util.*;
class Main {
public static void main(String args[]) {
// Your code goes here
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];

// input the array
for(int i=0;i<n;i++) {
arr[i] = scn.nextInt();
}

int target = scn.nextInt();
int fIndex = -1, lIndex = -1;
boolean found = false;

for(int i=0;i<n;i++) {
if(arr[i] == target) {
if(!found) {
fIndex = i;
lIndex = i;
found = true; //found for the first time
} else {
lIndex = i;
}
}
}

if(found == false) {
System.out.println("The element does not exist in the array");
} else {
System.out.println("First Index = " + fIndex + " Last Index = " + lIndex);
}
}
} 

Sample Output

When element exists

Input:
5
1 2 3 2 5
2

Output: First Index = 1 Last Index = 3

When the element does not exist

Input:
5
1 2 3 2 5
2

Output:The element does not exist in the array.


  • Corner Cases, You might Miss: The corner case of elements not present in the array is something that should be taken care of separately. In our code, we use the boolean variable found to do so. Otherwise, we can directly see if the values of fIndex and lIndex variables are -1 or not.


  • Time Complexity: O(N) as we are traversing the array.


  • Auxiliary Space: O(1) as we have not used any extra space to solve the problem.


Discussion

No Comment Found

Related InterviewSolutions