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
The Java solution for this problem employs a simple comparison technique where each element from nums1 is found in nums2, and the subsequent greater element is searched. This solution, albeit easy to understand, can be computationally expensive.
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#include <stdio.h>
2#include <stdlib.h>
3
4#define SIZE 10000
5
6struct Stack {
7 int top;
8 int items[SIZE];
9};
10
11void push(struct Stack* s, int x) {
12 s->items[++s->top] = x;
13}
14
15int pop(struct Stack* s) {
16 return s->items[s->top--];
17}
18
19int isEmpty(struct Stack* s) {
20 return s->top == -1;
21}
22
23int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
24 int* result = (int*)malloc(nums1Size * sizeof(int));
25 *returnSize = nums1Size;
26 int map[SIZE];
27 for (int i = 0; i < SIZE; i++) {
28 map[i] = -1;
29 }
30
31 struct Stack s;
32 s.top = -1;
33
34 for (int i = 0; i < nums2Size; i++) {
35 while (!isEmpty(&s) && s.items[s.top] < nums2[i]) {
36 map[s.items[s.top]] = nums2[i];
37 pop(&s);
38 }
39 push(&s, nums2[i]);
40 }
41
42 for (int i = 0; i < nums1Size; i++) {
43 result[i] = map[nums1[i]];
44 }
45 return result;
46}
47
48int main() {
49 int nums1[] = {4, 1, 2};
50 int nums2[] = {1, 3, 4, 2};
51 int returnSize;
52 int* result = nextGreaterElement(nums1, 3, nums2, 4, &returnSize);
53 for (int i = 0; i < returnSize; ++i) {
54 printf("%d ", result[i]);
55 }
56 free(result);
57 return 0;
58}This C solution builds an efficient resolution using a combination of a stack and hashmap. As elements traverse, unmatched elements are pushed onto the stack. When a larger element appears, it is stored in the hashmap mapped to the popped stack elements. This efficient solution runs in O(n) where n is nums2.length.