पुढील ग्रेटर एलिमेंट I लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन ब्लूमबर्ग
स्टॅक

समस्या विधान

या समस्येमध्ये, आम्हाला दोन याद्या देण्यात आल्या आहेत ज्यात प्रथम यादी दुसर्‍या यादीचा सबसेट आहे. पहिल्या यादीतील प्रत्येक घटकासाठी, आम्हाला दुसर्‍या यादीमध्ये पुढील मोठे घटक शोधावे लागतील.

पुढील ग्रेटर एलिमेंट I लीटकोड सोल्यूशन

उदाहरण

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

स्पष्टीकरण:

यादी 1 च्या पहिल्या घटकासाठी म्हणजे 4 साठी यादी 2 मध्ये पुढील कोणताही मोठा घटक नाही, म्हणून त्याचे उत्तर -1 आहे.
यादी 1 च्या दुसर्‍या घटकासाठी म्हणजे 1 साठी यादी 3 मधील 1 पेक्षा 2 मोठे आहे, अशा प्रकारे त्याचे उत्तर 3 आहे.
list1 च्या तिसर्‍या घटकासाठी म्हणजेच 2 साठी list2 मध्ये पुढील कोणताही मोठा घटक नाही, म्हणून त्याचे उत्तर -1 आहे.

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

दृष्टीकोन 1 (क्रूर शक्ती)

या पध्दतीमध्ये, आपण लूपसाठी नेस्टेड वापरुन list1 मध्ये रेषात्मक ट्रॅव्हर्सल करून list2 च्या प्रत्येक घटकासाठी पुढील मोठे घटक शोधू.
सूची 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 लीटकोड सोल्यूशनसाठी जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एम * एन): संख्या 1 च्या प्रत्येक घटकासाठी आपण डाव्या वरुन डाव्या बाजूस क्रमांकासह क्रमांक 2 शोधत आहोत. अशा प्रकारे, वेळ जटिलता हे ओ (एम * एन) आहे जेथे एम आणि एन यादीची लांबी आहेत.

स्पेस कॉम्प्लेक्सिटी 

ओ (1): कोणतीही अतिरिक्त जागा वापरली गेली नाही (अ‍ॅन्स अ‍ॅरेसाठी वापरली जाणारी स्पेस मानली जात नाही कारण ती आवश्यक आहे).

दृष्टीकोन 2 (स्टॅक वापरुन)

या दृष्टिकोनात दोन भाग आहेत.
प्रथम, आम्ही रेषेच्या वेळी यादीतील प्रत्येक घटकाचा पुढील मोठा घटक मिळविण्यासाठी स्टॅक वापरत आहोत. प्रत्येक घटकाची पुढील मोठी घटिका ए मध्ये संग्रहित केली जाते नकाशा.
दुसरे म्हणजे, आम्ही नकाशा वापरुन आपल्या उत्तर अ‍ॅरेमध्ये यादी 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 च्या मागे फिरत आहोत. मग आम्ही उत्तरे जोडण्यासाठी list1 ट्रॅव्हर्स करत आहोत. तर, वेळ जटिलता ही दोन्ही याद्यांच्या लांबीची बेरीज आहे.

स्पेस कॉम्प्लेक्सिटी 

ओ (एन): आम्ही ओ (1) वेळेत कोणत्याही कीचे उत्तर शोधण्यासाठी नकाशा वापरत आहोत, अशा प्रकारे स्पेसची जटिलता ओ (एन) आहे.