ಮುಂದಿನ ಗ್ರೇಟರ್ ಎಲಿಮೆಂಟ್ I ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಬ್ಲೂಮ್ಬರ್ಗ್
ಸ್ಟಾಕ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಎರಡು ಪಟ್ಟಿಗಳನ್ನು ನೀಡಲಾಗಿದೆ, ಇದರಲ್ಲಿ ಮೊದಲ ಪಟ್ಟಿಯು ಎರಡನೇ ಪಟ್ಟಿಯ ಉಪವಿಭಾಗವಾಗಿದೆ. ಮೊದಲ ಪಟ್ಟಿಯ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ, ಎರಡನೇ ಪಟ್ಟಿಯಲ್ಲಿ ಮುಂದಿನ ಹೆಚ್ಚಿನ ಅಂಶವನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ.

ಮುಂದಿನ ಗ್ರೇಟರ್ ಎಲಿಮೆಂಟ್ I ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಉದಾಹರಣೆ

nums1 = [4,1,2], nums2 = [1,3,4,2]
[-1,3,-1]

ವಿವರಣೆ:

ಪಟ್ಟಿ 1 ರ ಮೊದಲ ಅಂಶಕ್ಕೆ ಅಂದರೆ 4 ಕ್ಕೆ ಪಟ್ಟಿ 2 ರಲ್ಲಿ ಮುಂದಿನ ಹೆಚ್ಚಿನ ಅಂಶಗಳಿಲ್ಲ, ಆದ್ದರಿಂದ ಅದರ ಉತ್ತರ -1.
ಪಟ್ಟಿ 1 ರ ಎರಡನೇ ಅಂಶಕ್ಕೆ ಅಂದರೆ 1 ಕ್ಕೆ ಪಟ್ಟಿ 3 ರಲ್ಲಿ 1 ಕ್ಕಿಂತ 2 ದೊಡ್ಡದಾಗಿದೆ, ಆದ್ದರಿಂದ ಅದರ ಉತ್ತರ 3 ಆಗಿದೆ.
ಪಟ್ಟಿ 1 ರ ಮೂರನೇ ಅಂಶಕ್ಕಾಗಿ ಅಂದರೆ 2 ಕ್ಕೆ ಪಟ್ಟಿ 2 ರಲ್ಲಿ ಮುಂದಿನ ದೊಡ್ಡ ಅಂಶಗಳಿಲ್ಲ, ಆದ್ದರಿಂದ ಅದರ ಉತ್ತರ -1.

nums1 = [2,4], nums2 = [1,2,3,4]
[3,-1]

ಅಪ್ರೋಚ್ 1 (ವಿವೇಚನಾರಹಿತ ಶಕ್ತಿ)

ಈ ವಿಧಾನದಲ್ಲಿ, ಪಟ್ಟಿ 1 ರಲ್ಲಿ ರೇಖೀಯ ಅಡ್ಡಹಾಯುವಿಕೆಯನ್ನು ಮಾಡುವ ಮೂಲಕ ಪಟ್ಟಿಯ 2 ರ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ಮುಂದಿನ ಹೆಚ್ಚಿನ ಅಂಶವನ್ನು ನಾವು ಕಂಡುಕೊಳ್ಳುತ್ತೇವೆ.
ಪಟ್ಟಿ 1 ರ ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಮೊದಲು ಪಟ್ಟಿ 2 ರಲ್ಲಿ ಹುಡುಕಲಾಗುತ್ತದೆ, ನಂತರ ಅದರ ಮುಂದಿನ ಹೆಚ್ಚಿನ ಅಂಶವನ್ನು ಹುಡುಕಲಾಗುತ್ತದೆ. ಫ್ಲ್ಯಾಗ್ ವೇರಿಯಬಲ್ ಬಳಸಿ ನಾವು ಇದನ್ನು ಮಾಡುತ್ತಿದ್ದೇವೆ. ಪಟ್ಟಿ 1 ರ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ, ಇದನ್ನು ಮೊದಲು ತಪ್ಪು ಎಂದು ಹೊಂದಿಸಲಾಗಿದೆ. ಪಟ್ಟಿ 2 ರಲ್ಲಿ ನಾವು ಅಂಶವನ್ನು ಕಂಡುಕೊಂಡಾಗ, ಅದನ್ನು ನಿಜ ಎಂದು ಹೊಂದಿಸಲಾಗಿದೆ. ಅದರ ನಂತರ, ಮುಂದಿನದನ್ನು ನಾವು ಕಂಡುಕೊಂಡಾಗ, ನಾವು ಅದನ್ನು ಮತ್ತೆ ಸುಳ್ಳು ಎಂದು ಹೊಂದಿಸುತ್ತೇವೆ. ಹಾಗೆ ಮಾಡುವುದರಿಂದ, ಆ ವೇರಿಯೇಬಲ್‌ಗಾಗಿ ಪಟ್ಟಿ 2 ರಲ್ಲಿ ಮುಂದಿನ ಯಾವುದೇ ದೊಡ್ಡ ಅಂಶವಿದೆ ಅಥವಾ ಯಾವುದೂ ಇಲ್ಲ ಎಂದು ನಾವು ತಿಳಿದುಕೊಳ್ಳುತ್ತೇವೆ.

  • ಫ್ಲ್ಯಾಗ್ ವೇರಿಯೇಬಲ್ ನಿಜವಾಗಿದ್ದರೆ, ಆ ಅಂಶಕ್ಕಾಗಿ ಮುಂದಿನ ಯಾವುದೇ ಹೆಚ್ಚಿನ ಮೌಲ್ಯವನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಲಾಗಲಿಲ್ಲ ಎಂದರ್ಥ.
  • ಫ್ಲ್ಯಾಗ್ ವೇರಿಯೇಬಲ್ ತಪ್ಪಾಗಿದ್ದರೆ, ಆ ಅಂಶಕ್ಕಾಗಿ ಮುಂದಿನ ಒಂದು ಹೆಚ್ಚಿನ ಮೌಲ್ಯವನ್ನು ನಾವು ಕಂಡುಕೊಂಡಿದ್ದೇವೆ ಎಂದರ್ಥ.

ಆದ್ದರಿಂದ, ಪ್ರತಿ ಆಂತರಿಕ ಲೂಪ್ನ ಕೊನೆಯಲ್ಲಿ, ಧ್ವಜ ಮೌಲ್ಯದ ಪ್ರಕಾರ ನಾವು -1 ಅನ್ನು ನಮ್ಮ ಉತ್ತರವಾಗಿ ಸೇರಿಸುತ್ತೇವೆ.

ಮುಂದಿನ ಗ್ರೇಟರ್ ಎಲಿಮೆಂಟ್ I ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <iostream>
#include <vector>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        for(int i=0;i<nums1.size();i++){
            bool flag=false;
            for(int j=0;j<nums2.size();j++){
                if(nums1[i]==nums2[j])flag=true;
                if(flag && nums1[i]<nums2[j]){
                    ans.push_back(nums2[j]);flag=false;break;
                }
            }
            if(flag)ans.push_back(-1);
            
        }
        return ans;
    }
int main()
{
    vector<int> nums1{ 4,1,2 }; 
    vector<int> nums2{ 1,3,4,2 }; 
    vector<int>ans=nextGreaterElement(nums1,nums2);
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
}
-1 3 -1

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

import java.util.*;
import java.lang.*;

class Solution
{  
    public static void main(String args[])
    {
        int[]nums1={4,1,2};
        int[]nums2={1,3,4,2};
        int[]ans=nextGreaterElement(nums1,nums2);
        for(int i:ans){
            System.out.print(i+" ");
        }
            
        
    }
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[]ans=new int[nums1.length];
        for(int i=0;i<nums1.length;i++){
            boolean flag=false;
            for(int j=0;j<nums2.length;j++){
                if(nums1[i]==nums2[j])flag=true;
                if(flag && nums1[i]<nums2[j]){
                    ans[i]=nums2[j];flag=false;break;
                }
            }
            if(flag)ans[i]=-1;
            
        }
        return ans;
    }
}
-1 3 -1

ಮುಂದಿನ ಗ್ರೇಟರ್ ಎಲಿಮೆಂಟ್ I ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಮೀ * ಎನ್): Nums1 ನ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ನಾವು ಎಡದಿಂದ ಬಲಕ್ಕೆ nums2 ಅನ್ನು ರೇಖೀಯವಾಗಿ ಸಾಗಿಸುತ್ತಿದ್ದೇವೆ. ಆದ್ದರಿಂದ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು O (m * n) ಆಗಿದ್ದು, ಇಲ್ಲಿ m ಮತ್ತು n ಪಟ್ಟಿಗಳ ಉದ್ದವಾಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (1): ಯಾವುದೇ ಹೆಚ್ಚುವರಿ ಜಾಗವನ್ನು ಬಳಸಲಾಗಿಲ್ಲ (ಅನ್ಸ್ ಅರೇಗಾಗಿ ಬಳಸಿದ ಅಂತರವನ್ನು ಪರಿಗಣಿಸಲಾಗುವುದಿಲ್ಲ ಏಕೆಂದರೆ ಅದು ಅವಶ್ಯಕವಾಗಿದೆ).

ಅಪ್ರೋಚ್ 2 (ಸ್ಟಾಕ್ ಬಳಸಿ)

ಈ ವಿಧಾನವು ಎರಡು ಭಾಗಗಳನ್ನು ಒಳಗೊಂಡಿದೆ.
ಮೊದಲನೆಯದಾಗಿ, ಪಟ್ಟಿ 2 ರ ಪ್ರತಿಯೊಂದು ಅಂಶದ ಮುಂದಿನ ಹೆಚ್ಚಿನ ಅಂಶವನ್ನು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಪಡೆಯಲು ನಾವು ಸ್ಟಾಕ್ ಅನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ. ಪ್ರತಿ ಅಂಶದ ಮುಂದಿನ ಹೆಚ್ಚಿನ ಅಂಶವನ್ನು a ನಲ್ಲಿ ಸಂಗ್ರಹಿಸಲಾಗಿದೆ ನಕ್ಷೆ.
ಎರಡನೆಯದಾಗಿ, ನಕ್ಷೆಯನ್ನು ಬಳಸಿಕೊಂಡು ನಮ್ಮ ಉತ್ತರ ಶ್ರೇಣಿಯಲ್ಲಿನ ಪಟ್ಟಿ 1 ರ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ನಾವು ಉತ್ತರವನ್ನು ಸಂಗ್ರಹಿಸುತ್ತೇವೆ.

ಆದ್ದರಿಂದ, ನಾವು ಪಟ್ಟಿ 2 ಅನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ ಮತ್ತು ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಸ್ಟ್ಯಾಕ್‌ನ ಮೇಲ್ಭಾಗದಿಂದ ಪ್ರಸ್ತುತ ಸಂಖ್ಯೆಗೆ ಚಿಕ್ಕದಾಗಿದೆ ಮತ್ತು ಏಕಕಾಲದಲ್ಲಿ ಪಾಪ್ ಮಾಡುತ್ತೇವೆ, ಪ್ರತಿ ಪಾಪ್‌ನಲ್ಲಿ ನಾವು ಪ್ರಸ್ತುತ ಅಂಶವನ್ನು ಪ್ರತಿ ಪಾಪ್ ಮಾಡಿದ ಅಂಶದ ಹತ್ತಿರದ ಉತ್ತರವಾಗಿ ದಾಖಲಿಸುತ್ತೇವೆ. ಈ ಮ್ಯಾಪಿಂಗ್ಗಾಗಿ, ನಾವು ಸರಳವಾಗಿ ನಕ್ಷೆಯನ್ನು ಬಳಸುತ್ತೇವೆ.
ಈಗ, ನಾವು ನಕ್ಷೆಯನ್ನು ಹೊಂದಿದ್ದೇವೆ, ಅದು ಅವುಗಳ ಮುಂದಿನ ಹೆಚ್ಚಿನ ಅಂಶಗಳೊಂದಿಗೆ ಅಂಶಗಳ ಮ್ಯಾಪಿಂಗ್ ಆಗಿದೆ.
ಅಂತಿಮವಾಗಿ, ನಾವು ಪಟ್ಟಿ 1 ಅನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ ಮತ್ತು ಅವುಗಳ ಮೌಲ್ಯಗಳನ್ನು ನಕ್ಷೆಯಿಂದ ನಮ್ಮ ಉತ್ತರ ಪಟ್ಟಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ.

ಮುಂದಿನ ಗ್ರೇಟರ್ ಎಲಿಮೆಂಟ್ I ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <iostream>
#include <vector>
#include <stack>
#include <map>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int>stack;
        map<int,int>map;
        vector<int>ans;
        for(int i=0;i<nums2.size();i++){
            while(!stack.empty()){
                if(stack.top()<nums2[i]){
                    map.insert(pair<int,int>(stack.top(),nums2[i]));
                    stack.pop();
                }else break;
            }
            stack.push(nums2[i]);
        }
        
        for(int i=0;i<nums1.size();i++){
            int val = map[nums1[i]];
            if(val==0)ans.push_back(-1);
            else ans.push_back(val);
        }
        return ans;
    }
int main()
{
    vector<int> nums1{ 4,1,2 }; 
    vector<int> nums2{ 1,3,4,2 }; 
    vector<int>ans=nextGreaterElement(nums1,nums2);
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
}
-1 3 -1

ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

import java.util.*;
import java.lang.*;

class Solution
{  
    public static void main(String args[])
    {
        int[]nums1={4,1,2};
        int[]nums2={1,3,4,2};
        int[]ans=nextGreaterElement(nums1,nums2);
        for(int i:ans){
            System.out.print(i+" ");
        }
            
        
    }
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer>stack=new Stack<Integer>();
        Map<Integer,Integer>map=new HashMap<Integer,Integer>();
        int[]ans=new int[nums1.length];
        for(int i:nums2){
            while(!stack.isEmpty()){
                if(stack.peek()<i){
                    map.put(stack.peek(),i);
                    stack.pop();
                }else break;
            }
            stack.push(i);
        }
        for(int i=0;i<nums1.length;i++){
            if(map.containsKey(nums1[i]))
            ans[i]=map.get(nums1[i]);
            else ans[i]=-1;
        }
        return ans;
    }
}
-1 3 -1

ಮುಂದಿನ ಗ್ರೇಟರ್ ಎಲಿಮೆಂಟ್ I ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಮೀ + ಎನ್): ಮೊದಲನೆಯದಾಗಿ, ಪಟ್ಟಿ 2 ರ ಎಲ್ಲಾ ಅಂಶಗಳಿಗೆ ಮುಂದಿನ ಹೆಚ್ಚಿನ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ಪಟ್ಟಿ 2 ಅನ್ನು ಹಾದುಹೋಗುತ್ತಿದ್ದೇವೆ. ನಂತರ, ಉತ್ತರಗಳನ್ನು ಸೇರಿಸಲು ನಾವು ಪಟ್ಟಿ 1 ಅನ್ನು ಹಾದುಹೋಗುತ್ತಿದ್ದೇವೆ. ಆದ್ದರಿಂದ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಎರಡೂ ಪಟ್ಟಿಗಳ ಉದ್ದದ ಮೊತ್ತವಾಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (ಎನ್): ಒ (1) ಸಮಯದಲ್ಲಿ ಯಾವುದೇ ಕೀಲಿಯ ಉತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು ನಕ್ಷೆಯನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ, ಹೀಗಾಗಿ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯು ಒ (ಎನ್) ಆಗಿದೆ.