CC-1 : Find first and last index of given number in an array.

Description:

Given an input integer array "arr" and an integer "searchInt", find the first and last index of searchInt in arr.

Test cases and expected outputs:

Input Parameters	Expected outputs
arr={1,2,3,4,5,6,7,1}, searchInt=1	firstIdx=0, lastIdx=7
arr={1,2,3,4,5,6,7,1}, searchInt=3	firstIdx=2, lastIdx=2
arr={1,2,3,4,5,6,7,1}, searchInt=11	firstIdx=-1, lastIdx=-1

Asked by:

,

Leetcode #34

Summary Algorithm:

Initialize two tracking variables to -1 and iterate through the entire array to locate the specified target value. When a match is found, the algorithm records the index as the first occurrence if it hasn't been set yet and continually updates the last occurrence index until the loop finishes.

Pseudocode:

The method should accept following input parameters: arr (int array), searchInt (integer to be searched in arr).

Initialize 2 variables firstIdx and lastIdx to -1. We will use these variables to track the first and last index of searchInt in arr.

Iterate through arr using a for loop, using variable idx as loop counter:

If searchInt is found for first time set firstIdx and lastIdx to the index at which it was found.

If searchInt is found again in any iteration just update lastIdx to the index at which it was found.

Add firstIdx and lastIdx to an integer array and return the same.

Code:

public int[] arrayFindFirstAndLastIndexOfElement(int[] arr,int searchInt) throws Exception{
	int firstIdx=-1;
	int lastIdx=-1;
	for (int idx=0; idx < arr.length; idx++) {
		if (arr[idx] == searchInt) {
			if (firstIdx==-1) {
				firstIdx=idx;
				lastIdx=idx;
			}else {
				lastIdx=idx;
			}				
		}			
	}
	int[] idxFound=new int[2];
	if (firstIdx==-1) {
		idxFound[0]=idxFound[1]=-1;
	}else {
		idxFound[0]=firstIdx;
		idxFound[1]=lastIdx;
	}
	return idxFound;			
}

Time Complexity	Space Complexiy
O(n)	O(1)

Click here for execution trace to understand the code better.

Step / idx	arr[idx]	arr[idx] == 1	firstIdx	lastIdx	Action / Logic
Initial	-	-	-1	-1	Variables initialized.
0	1	true	0	0	Match! `firstIdx` was -1, so set both `firstIdx` and `lastIdx` to 0.
1	2	false	0	0	No match. Continue.
2	3	false	0	0	No match. Continue.
3	4	false	0	0	No match. Continue.
4	5	false	0	0	No match. Continue.
5	6	false	0	0	No match. Continue.
6	7	false	0	0	No match. Continue.
7	1	true	0	7	Match! `firstIdx` is already 0, so update `lastIdx` to 7.
Final result returned: [0, 7]

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class ArrayFindFirstAndLastIndexOfElement {
	
public int[] arrayFindFirstAndLastIndexOfElement(int[] arr,int searchInt) throws Exception{
	int firstIdx=-1;
	int lastIdx=-1;
	for (int idx=0; idx < arr.length; idx++) {
		if (arr[idx] == searchInt) {
			if (firstIdx==-1) {
				firstIdx=idx;
				lastIdx=idx;
			}else {
				lastIdx=idx;
			}				
		}			
	}
	int[] idxFound=new int[2];
	if (firstIdx==-1) {
		idxFound[0]=idxFound[1]=-1;
	}else {
		idxFound[0]=firstIdx;
		idxFound[1]=lastIdx;
	}
	return idxFound;			
}
	
	
public static void main(String[] args) {
	try {
	ArrayFindFirstAndLastIndexOfElement ap=new ArrayFindFirstAndLastIndexOfElement();
	int[] intArray1 = {1,2,3,4,5,6,7,1};
	printArraySummary(intArray1, "Original Array:");
	int[] indices=ap.arrayFindFirstAndLastIndexOfElement(intArray1,1);
	System.out.print("\nFirst and Last Index of a particular number"+ 1 +" in the array:\n");
	if (indices[0]==-1) {
		System.out.print("\n\n Required number not found in Array! \n");
	}else {
		System.out.print("\n\n First index of array where required number was found is ["+indices[0]+"] \n");
			System.out.print("\n\n Last index of array where required number was found is ["+indices[1]+"] \n");
	}	
	
	int[] intArray2 = {1,2,3,4,5,6,7,1};
	printArraySummary(intArray2, "Original Array:");
	indices=ap.arrayFindFirstAndLastIndexOfElement(intArray1,3);
	System.out.print("\nFirst and Last Index of a particular number "+3+" in the array:\n");
	if (indices[0]==-1) {
		System.out.print("\n\n Required number not found in Array! \n");
	}else {
		System.out.print("\n\n First index of array where required number was found is ["+indices[0]+"] \n");
		System.out.print("\n\n Last index of array where required number was found is ["+indices[1]+"] \n");
	}
	
	int[] intArray3 = {1,2,3,4,5,6,7,1};
	printArraySummary(intArray3, "Original Array:");
	indices=ap.arrayFindFirstAndLastIndexOfElement(intArray1,11);
	System.out.print("\nFirst and Last Index of a particular number "+ 11+" in the array:\n");
	if (indices[0]==-1) {
		System.out.print("\n\n Required number not found in Array! \n");
	}else {
	System.out.print("\n\n First index of array where required number was found is ["+indices[0]+"] \n");
	System.out.print("\n\n Last index of array where required number was found is ["+indices[1]+"] \n");
	}
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
	}
				
	}
	
	
public static void printArraySummary(int[] intArray, String label) throws Exception {
	// Case 1: The input Array is null !!
    if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
    	// Case 2: Print input Array by index (first to last)
		System.out.println();
		System.out.println("************************************************************************");
		System.out.print(label+" : ");
		int arrayIndex=0;
		for (arrayIndex=0; arrayIndex < intArray.length; arrayIndex++) {
				System.out.print(intArray[arrayIndex]);
				if (arrayIndex< intArray.length-1) {System.out.print(",");}
		} 
	System.out.println();
	System.out.println("************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}

}