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 <stdio.h>
2#include <stdlib.h>
3
4int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
5 int* result = (int*)malloc(nums1Size * sizeof(int));
6 *returnSize = nums1Size;
7 for(int i = 0; i < nums1Size; ++i) {
8 int found = 0, j;
9 for(j = 0; j < nums2Size; ++j) {
10 if(nums2[j] == nums1[i]) {
11 found = 1;
12 break;
13 }
14 }
15 if(found) {
16 int nextGreater = -1;
17 for(j = j + 1; j < nums2Size; ++j) {
18 if(nums2[j] > nums1[i]) {
19 nextGreater = nums2[j];
20 break;
21 }
22 }
23 result[i] = nextGreater;
24 }
25 }
26 return result;
27}
28
29int main() {
30 int nums1[] = {4, 1, 2};
31 int nums2[] = {1, 3, 4, 2};
32 int returnSize;
33 int* result = nextGreaterElement(nums1, 3, nums2, 4, &returnSize);
34 for (int i = 0; i < returnSize; ++i) {
35 printf("%d ", result[i]);
36 }
37 free(result);
38 return 0;
39}This C solution uses nested looping to find the next greater element by directly comparing elements. The outer loop iterates through nums1, and for each element, it finds its position in nums2 using another loop. Then, it looks for the next greater element from that position. Although simple, this solution can be improved in terms of efficiency.
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.
1using System.Collections.Generic;
public class NextGreaterElementOptimized {
public int[] NextGreaterElement(int[] nums1, int[] nums2) {
Dictionary<int, int> map = new Dictionary<int, int>();
Stack<int> stack = new Stack<int>();
foreach (int num in nums2) {
while (stack.Count > 0 && stack.Peek() < num) {
map[stack.Pop()] = num;
}
stack.Push(num);
}
for (int i = 0; i < nums1.Length; i++) {
nums1[i] = map.ContainsKey(nums1[i]) ? map[nums1[i]] : -1;
}
return nums1;
}
public static void Main() {
int[] nums1 = { 4, 1, 2 };
int[] nums2 = { 1, 3, 4, 2 };
var obj = new NextGreaterElementOptimized();
int[] result = obj.NextGreaterElement(nums1, nums2);
Console.WriteLine(string.Join(", ", result));
}
}This C# solution uses a stack and hashmap to efficiently map elements from nums2 to find their next greater numbers. By building the hashmap beforehand, the transformation into the result array for nums1 is highly optimized.