Star Elements
Problem Descriptionβ
Given an unsorted array arr
of size n
. The task is to find all the star and super star elements in the array. Star are those elements which are strictly greater than all the elements on its right side. Super star are those elements which are strictly greater than all the elements on its left and right side.
Note: Assume first element (arr[0]
) is greater than all the elements on its left side, And last element (arr[n-1])
is greater than all the elements on its right side.
Examplesβ
Example 1:
Input:
n = 10
arr[] = {1, 6, 5, 4, 7, 8, 4, 3, 2, 1}
Output:
8 4 3 2 1
8
Explanation: Star elements are 8, 4, 3, 2 and 1.
Super star element is 8.
Example 2:
Input:
a = 9
arr[] = {1, 2, 10, 3, 4, 5, 8, 10, 4}
Output:
10 4
-1
Explanation: Star elements are 10 and 4.
No super star element present here.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraintsβ
1 β€ N β€ 10^6
Problem Explanationβ
The task is to traverse the array and search the number.
Code Implementationβ
C++ Solutionβ
#include <iostream>
using namespace std;
void findStars(int arr[], int n) {
int maxRight = arr[n-1];
cout << "Super Stars: ";
for (int i = n-1; i >= 0; i--) {
if (arr[i] > maxRight) {
cout << arr[i] << " ";
maxRight = arr[i];
}
}
cout << endl;
cout << "Stars: ";
maxRight = arr[n-1];
for (int i = n-2; i >= 0; i--) {
if (arr[i] > maxRight) {
cout << arr[i] << " ";
maxRight = arr[i];
}
}
cout << endl;
}
int main() {
int arr[] = {4, 6, 3, 7, 2, 8};
int n = sizeof(arr)/sizeof(arr[0]);
findStars(arr, n);
return 0;
}
public class Main {
public static void findStars(int[] arr) {
int maxRight = arr[arr.length-1];
System.out.print("Super Stars: ");
for (int i = arr.length-1; i >= 0; i--) {
if (arr[i] > maxRight) {
System.out.print(arr[i] + " ");
maxRight = arr[i];
}
}
System.out.println();
System.out.print("Stars: ");
maxRight = arr[arr.length-1];
for (int i = arr.length-2; i >= 0; i--) {
if (arr[i] > maxRight) {
System.out.print(arr[i] + " ");
maxRight = arr[i];
}
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {4, 6, 3, 7, 2, 8};
findStars(arr);
}
}
def find_stars(arr):
max_right = arr[-1]
super_stars = []
for i in range(len(arr)-1, -1, -1):
if arr[i] > max_right:
super_stars.append(arr[i])
max_right = arr[i]
print("Super Stars:", super_stars)
max_right = arr[-1]
stars = []
for i in range(len(arr)-2, -1, -1):
if arr[i] > max_right:
stars.append(arr[i])
max_right = arr[i]
print("Stars:", stars)
arr = [4, 6, 3, 7, 2, 8]
find_stars(arr)
function findStars(arr) {
let maxRight = arr[arr.length-1];
let superStars = [];
for (let i = arr.length-1; i >= 0; i--) {
if (arr[i] > maxRight) {
superStars.push(arr[i]);
maxRight = arr[i];
}
}
console.log("Super Stars:", superStars);
maxRight = arr[arr.length-1];
let stars = [];
for (let i = arr.length-2; i >= 0; i--) {
if (arr[i] > maxRight) {
stars.push(arr[i]);
maxRight = arr[i];
}
}
console.log("Stars:", stars);
}
Solution Logic:β
- Initialize maxRight to the last element of the array.
- Iterate through the array from right to left (starting from the second last element).
- For each element, check if it is greater than maxRight. If it is, add it to the stars array and update maxRight.
- Repeat steps 2-3 until the beginning of the array is reached.
- To find super stars, repeat steps 2-4, but add elements to the superStars array only if they are greater than maxRight and also greater than all elements on their left side.
Time Complexityβ
- The time complexity is where n is the input number.
Space Complexityβ
- The auxiliary space complexity is due to the only extra memory used is for temporary variables while swapping two values in Array.