Sponsored
Sponsored
This approach involves iterating over each element of nums1 and finding the corresponding element in nums2. Once located, search for the next greater element to its right. This straightforward method checks each pair and ensures correctness but may not be optimal for larger arrays.
The time complexity of this brute force approach is O(n * m), where n is the number of elements in nums1, and m is the number of elements in nums2. The space complexity is O(1) apart from the output array.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
6 vector<int> res;
7 for (int i = 0; i < nums1.size(); ++i) {
8 int j = 0;
9 while (j < nums2.size() && nums2[j] != nums1[i]) ++j;
10 int k = j + 1;
11 while (k < nums2.size() && nums2[k] <= nums1[i]) ++k;
12 res.push_back(k < nums2.size() ? nums2[k] : -1);
13 }
14 return res;
15}
16
17int main() {
18 vector<int> nums1 = {4, 1, 2};
19 vector<int> nums2 = {1, 3, 4, 2};
20 vector<int> result = nextGreaterElement(nums1, nums2);
21 for (int num : result) {
22 cout << num << " ";
23 }
24 return 0;
25}This C++ solution implements the brute force approach by using index searching and comparison logic. It iterates through each element in nums1 and locates it in nums2 before checking for the next greater element to the right. This technique is implementationally straightforward but suboptimal due to O(n*m) time complexity.
This approach utilizes a stack and a hashmap to efficiently solve the problem. As we traverse nums2, we use the stack to store elements for which the next greater element hasn't been found yet. Whenever a greater element is found, it's recorded in the hashmap against the elements in the stack. This technique is optimal and runs in linear time.
The time complexity is O(n + m), approaching linear time with respect to input size and space is approximately O(m) for hashmap tracking.
1
Using both stack and hashmap, this Python solution processes nums2 entirely, updating the hashmap with the next greater elements as soon as they are found. The transformation into nums1 results is rapid due to pre-built mappings.