Problem to be solved:
You are given an unsorted array of integers, what is the optimal way to find the third largest number in the array? Note: the array contains duplicate values and negative values as well, and also this code should work if the array length increase by N number of times.
The solution is given in JAVA:
Example 1: Unsorted array with Negative values
Input: [87, 99, -14, 05, 46, 54]
Code:
public class ThirdLargestNumInArray {
public static void main(String[] args) {
/*
* unsorted Array with duplicate and negative values
*/
Integer arr[] = { 87, 99, -14, 05, 46, 54 };
/* Variable initialization */
int largest = 0, secondLargest = 0, thirdLargest = 0;
/* Condition to find */
for (int i = 0; i < arr.length; i++) {
if (arr[i] > largest) {
/*
* if condition is true assign large value to second large value
*/
secondLargest = largest;
/* assign new large value */
largest = arr[i];
} else if (arr[i] > secondLargest) {
/*
* if condition is true assign second large value to third large value
*/
thirdLargest = secondLargest;
/* assign new second large value */
secondLargest = arr[i];
} else if (arr[i] > thirdLargest) {
/*
* if condition is true the third largest value will be assigned
*/
thirdLargest = arr[i];
}
}
/* Print the values */
System.out.println("Largest = " + largest);
System.out.println("Second Largest = " + secondLargest);
System.out.println("Third Largest = " + thirdLargest);
}
}
Output:
Largest = 99
Second Largest = 87
Third Largest = 54
Explanation:
As mentioned above the array is initialized with both positive and negative values
We are initialized variables to store the largest, second largest and third largest respectively. Note: variables are initialized with 0 for one special case which is, if 3rd max element is not present in the array then it will return 0.
Iterate the loop N(length of the array) number time to find the 3 largest value.
If condition is to assign large value to second large value and initialize the new large value in the array.
1st elseif condition is to assign second large value to third large value and initialize the new second large value in the array.
2nd elseif condition is to assign third large value in the array.Finally print the variables.
Example 2: Unsorted array with negative and duplicate values
Input: [77, 101, 95, 14, 05, 46, -47, 94, 00, 95, 52, 86, 36, -54, 94, 89]
Code:
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
public class ThirdLargestNumInSet {
public static void main(String[] args) {
/*
* unsorted Array with duplicate and negative values
*/
Integer arr[] = { 77, 101, 14, 05, 46, -47, 94, 00, 95, 52, 86, 36, -54, 94, 89 };
/* Variable initialization */
int largest = 0, secondLargest = 0, thirdLargest = 0;
/*
* using LinkedHashSet - Map to remove duplication in Array
*/
Set<Integer> newSet = new LinkedHashSet<>();
for (int i = 0; i < arr.length; i++) {
newSet.add(arr[i]);
}
/* Condition to find */
for (Integer i : newSet) {
if (i > largest) {
/*
* if condition is true assign large value to second large value
*/
secondLargest = largest;
/* assign new large value */
largest = i;
} else if (i > secondLargest) {
/*
* if condition is true assign second large value to third large value
*/
thirdLargest = secondLargest;
/* assign new second large value */
secondLargest = i;
} else if (i > thirdLargest) {
/*
* if condition is true the third largest value will be assigned
*/
thirdLargest = i;
}
}
/* Print the values */
System.out.print("Largest = " + largest);
System.out.print("\nSecond Largest = " + secondLargest);
System.out.print("\nThird Largest = " + thirdLargest);
}
}
Output:
Largest = 101
Second Largest = 95
Third Largest = 94
Explanation:
The pseudocode used in both codes are same but only diference in Example 02 is we use LinkedHashSet which is a Java collections where we store unique objects this result in removal of duplicate values in the array.
Other Preference :
We can use Bubble Sort Algorithm (sort by smallest to largest order) to sort the array and find the largest value of the array.
Input: [87, 99, 14, 05, 46, 54]
Code:
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
public class Main {
public static void bubblesort(Integer[] arr) {
int n = arr.length;
int temp;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
Integer[] arr = { 87, 99, 14, 05, 46, 54 };
bubblesort(arr);
System.out.print("array after sorting : ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
int n = arr.length;
int max = arr[n - 3];
System.out.println("\n3rd largest value: " + max);
}
}
Output:
array after sorting : 5 14 46 54 87 99
3rd largest value: 54
Special Note: I came up with this solution after facing an interview which is to find O(n) time complexity for code without having O(n^2) time complexity. Hope this will help someone in future!! I welcome your feedback and solutions-oriented suggestions, thank you for your time
Happy Coding❤️❤️❤️
Top comments (0)