703050. Greater on right side
Greater on right side
Summary
Given an array of integers, write a program to find all elements that are greater than or equal to at least one element on its right side. This problem involves arrays and data structures, which is relevant for the tags "Arrays" and "Data Structures". The difficulty level is marked as Easy.
Detailed Explanation
The given task can be achieved by iterating through the array from left to right. For each element, check if it's greater than or equal to any of the elements on its right side. If an element is found that meets this condition, include it in the result set. The final output will consist of all elements that have a value greater than or equal to at least one element on their right side.
Here's a step-by-step breakdown:
- Initialize an empty array or list to store the results.
- Start from the leftmost element of the original array.
- For each element, iterate through the remaining elements to its right.
- Check if the current element is greater than or equal to any of the elements on its right side.
- If yes, add this element to the result set.
- Continue this process for all elements in the array.
Time complexity: O(n^2), where n is the number of elements in the array. This occurs because we're iterating through each element and then again through the remaining elements on its right side.
Space complexity: O(n), as we're storing the result set, which has a maximum size equal to the input array's size.
Optimized Solutions
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 2, 4};
findGreater(arr);
}
public static void findGreater(int[] arr) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
boolean greater = false;
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] >= arr[j]) {
greater = true;
break;
}
}
if (greater) {
result.add(arr[i]);
}
}
System.out.println(result);
}
}