Skip to main content

Equal Beauty CodeChef SnackDown 2021 Round 1A

 Equal Beauty CodeChef SnackDown 2021 Round 1A Question The beauty of an (non-empty) array of integers is defined as the difference between its largest and smallest element. For example, the beauty of the array [2,3,4,4,6] is 6−2=4. An array A is said to be good if it is possible to partition the elements of A into two non-empty arrays B1 and B2 such that B1 and B2 have the same beauty. Each element of array A should be in exactly one array: either in B1 or in B2. For example, the array [6,2,4,4,4] is good because its elements can be partitioned into two arrays B1=[6,4,4] and B2=[2,4], where both B1 and B2 have the same beauty (6−4=4−2=2). You are given an array A of length N. In one move you can: Select an index i (1≤i≤N) and either increase Ai by 1 or decrease Ai by 1. Find the minimum number of moves required to make the array A good. Input Format The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow. Each ...
Post a Comment

Next Greater Element I LeetCode Solution

 Next Greater Element I LeetCode Solution

Next Greater Element I LeetCode


Question

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

 

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

 

Constraints:

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • All integers in nums1 and nums2 are unique.
  • All the integers of nums1 also appear in nums2.

Explanation

This question is categorized in the easy section of LeetCode. This question can be solved in many approaches even due to the small constraints Brute Force approach will also work. Here we will explain the optimized approach using Maps, Stacks although brute force approach is also shown in the solutions given below. First we are discussing the approach used in python code. Sizes of both arrays are small enough, so we just can do brute-force solution in O(m * n), where n is size of nums2 and m is size of nums1. If we want to solve this problem in O(n) time, it is not so simple. The idea is to traverse nums2 and keep stack with decreasing order of elements. When we try to add element, if it is less than last element of stack, we just add it. If it is more than the last element, we extract it from stack and also put it inside dic: correspondence between numbers and its next greater element: we need it, because we have also nums1, which we need to traverse after. Next, when we traverse nums1 we can use function .get(num, -1), which will return answer for num if it is inside dictionary and -1 if it was not found. Now we are discussing a bit for the brute force approach The given could have been easily stated as given int arrays nums1 and nums2, for each number x in nums1, find the next greater number after x appearing in nums2. The algorithm below is generally basic and you can also solve it using a monotonically increasing stack. The first part of the algorithm is to convert nums2 into a map where it maps each number to an index. The second portion is to use a quadratic loop. The outer loop will iterate over all numbers in nums1 and the inner loop will iterate from where the number in nums1 is found in nums2 and find the next greater element. Once the next greater element is found, we can set result[i] = number in nums2 and move onto the next number in nums1. If not found, we just set result[i] = -1. Now discussing the optimized code for C++. Start traversing the nums2 array from last. Also create a stack & ans array. If current nums2[i] value is less than the stack top then simply push stack top to ans & then push nums2[i] to stack. If current nums2[i] value is greater than stack top then pop all values from stack until stack top is greater than nums2[i] or stack becomes empty. This is all we need to do, hope you understood the explanation. I recommend first to try the question yourself then if you are stuck you can approach the solutions given below in Java, C++, Python3, C#.

Program Code

Java 

Brute Force with memorization

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
var indexByNum = new HashMap<Integer, Integer>();
for (var i = 0; i < nums2.length; i++)
indexByNum.put(nums2[i], i);

var memo = new HashMap<Integer, Integer>();
var result = new int[nums1.length];

for (var i = 0; i < nums1.length; i++)
result[i] = getNextGreater(nums1[i], nums2, indexByNum, memo);
return result;
}

private int getNextGreater(int query, int[] nums2, Map<Integer, Integer> indexByNum, Map<Integer, Integer> memo) {
if (memo.containsKey(query))
return memo.get(query);
for (var i = indexByNum.get(query); i < nums2.length; i++)
if (nums2[i] > query) {
memo.put(query, nums2[i]);
return nums2[i];
}
memo.put(query, -1);
return -1;

Optimized Code 

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> hm =  new HashMap<>();
        int len2 = nums2.length;
        int count = 0;
        int [] ret = new int[nums1.length];
        for (int i=0;i<nums2.length;i++){
            hm.put(nums2[i],i);
        }
        for (int num : nums1){
                int index = hm.get(num) +1;
                ret[count] =-1;
                while (index<len2){
                    if (nums2[index]>num){
                        ret[count] = nums2[index];
                        break;
                    }
                    index++;
                }
                count++;
        }
        return ret;
    }
}


C++

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int n = nums2.size(),topp;
        unordered_map<int,int>mp;
        stack<int>s;
        vector<int>ans(n);
        
        for(int i=0;i<n;i++)
        {
            mp[nums2[i]]=i;
        }
        
        for(int i=n-1;i>=0;i--)
        {
            if(!s.empty())
            {
                topp = s.top();
                while(nums2[i] > topp && !s.empty())
                {
                    s.pop();
                    if(s.empty())
                        break;
                    
                    topp = s.top();
                }
                
                if(s.empty())
                {
                    ans[i]=-1;
                    s.push(nums2[i]);
                }
                else
                {
                    topp = s.top();
                    ans[i]=topp;
                    s.push(nums2[i]);
                }
            }
            else
            {
                ans[i]=-1;
                s.push(nums2[i]);
            }
        }
        
        int m = nums1.size();
        vector<int>v;
        
        for(int i=0;i<m;i++)
        {
            v.push_back(ans[mp[nums1[i]]]);
        }
        
        return v;
    }
};

Python3

def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
# Stores index of values in nums1
val_to_ind = {num:i for i, num in enumerate(nums1)}
# default answers
ans = [-1]*len(nums1)

n = len(nums2)
# first value in nums2 that is also in nums1
i = next(filter(lambda i: nums2[i] in val_to_ind, range(n)))
# Values for which we haven't found nextGreater, in descending order (stacked)
vals_left = [nums2[i]]
# Move forward in nums2, storing answers and unanswered values
for i in range(i+1, n):
# nums2[i] is next greater for smallest stored value
while vals_left and nums2[i]>vals_left[-1]:
# get smallest stored value, get its index in nums1, and update nextGreater at that index in ans
ans[val_to_ind.pop(vals_left.pop())] = nums2[i]
# is in nums1 (and is less than all values in vals_left because while loop exited, maintaining descending order in vals_left)
if nums2[i] in val_to_ind:
vals_left.append(nums2[i])

return ans


Another approach in Python3

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        greater = {}
        stack = []
        for num in nums2:
            while stack and stack[-1] < num:
                greater[stack.pop()] = num
            stack.append(num)
            
        return [greater.get(num, -1) for num in nums1]


C#

public int[] NextGreaterElement(int[] nums1, int[] nums2) {
var dict = new Dictionary<int, int>();
var stack = new Stack<int>();

foreach (var n in nums2) {
while (stack.Any() && stack.Peek() < n)
dict[stack.Pop()] = n;
stack.Push(n);
}

return nums1.Select(x => dict.GetValueOrDefault(x, -1)).ToArray();
}


More Information About LeetCode Daily Challenge

LeetCode is a great coding platform which provides daily problems to solve and maintain a streak of coding. This platform helps in improvement of coding skills and attempting the daily challenge makes our practice of coding regular. With its bunch of questions available it is one of the best coding platforms where you can have self improvement. LeetCode also holds weekly and biweekly contests which is a great place to implement you knowledge and coding skills which you learnt through out the week by performing the daily challenge. It also provides badges if a coder solves all the daily problems of a month. For some lucky winners T-shirts are also given and that too for free. If you get the pro version you can get more  from LeetCode like questions that are asked in interviews, detailed explanation of each chapter and each concept and much more. LeetCode challenges participants with a problem from our carefully curated collection of interview problems every 24 hours.
All users with all levels of coding background are welcome to join!
@PREMIUM USERS will have an extra carefully curated premium challenge weekly and earn extra LeetCoin rewards. The premium challenge will be available together with the first October challenge of the week and closed together with the November challenge of the week.
Starting from 2021, users who completed all Daily LeetCoding Challenge non-premium problems for the month (with or without using Time Travel Tickets) will win a badge to recognize their consistency! Your badges will be displayed on your profile page. Completing each non-premium daily challenge. (+10 LeetCoins)
Completing 25 to 30 non-premium daily challenges without using Time Travel Ticket will be eligible for an additional 25 LeetCoins. (Total = 275 to 325 LeetCoins)
Completing all 31 non-premium daily challenges without using Time Travel Ticket will be eligible for an additional 50 LeetCoins, plus a chance to win a secret prize ( Total = 385 LeetCoins + *Lucky Draw)!
Lucky Draw: Those who complete all 31 non-premium daily challenges will be automatically entered into a Lucky Draw, where LeetCode staff will randomly select 3 lucky participants to each receive one LeetCode Polo Shirt on top of their rewards! Do you have experience trying to keep a streak but failed because you missed one of the challenges?
Hoping you can travel back to the missed deadline to complete the challenge but that's not possible......or is it?
With the new Time Travel Ticket , it's possible! In order to time travel, you will need to redeem a Time Travel Ticket with your LeetCoins. You can redeem up to 3 tickets per month and the tickets are only usable through the end of the month in which they are redeemed but you can use the tickets to make up any invalid or late submission of the current year. To join, just start solving the daily problem on the calendar of the problem page. You can also find the daily problem listed on the top of the problem page. No registration is required. The daily problem will be updated on every 12 a.m. Coordinated Universal Time (UTC) and you will have 24 hours to solve that challenge. Thar's all you needed to know about Daily LeetCode Challenge.
Labels:

Comments

Post a Comment

Popular posts from this blog

Snake Procession CodeChef SnackDown 2021 Beginner Practice Contest

 Snake Procession CodeChef SnackDown 2021 Beginner Practice Contest Question: The annual snake festival is upon us, and all the snakes of the kingdom have gathered to participate in the procession. Chef has been tasked with reporting on the procession, and for this he decides to first keep track of all the snakes. When he sees a snake first, it'll be its Head, and hence he will mark a 'H'. The snakes are long, and when he sees the snake finally slither away, he'll mark a 'T' to denote its tail. In the time in between, when the snake is moving past him, or the time between one snake and the next snake, he marks with '.'s. Because the snakes come in a procession, and one by one, a valid report would be something like "..H..T…HTH….T.", or "…", or "HT", whereas "T…H..H.T", "H..T..H", "H..H..T..T" would be invalid reports (See explanations at the bottom). Formally, a snake is represented by a 'H...
Post a Comment
Read more

Qualifying to Pre-Elimination CodeChef SnackDown 2021 Beginner Practice Contest

 Qualifying to Pre-Elimination  CodeChef SnackDown 2021 Beginner Practice Contest Question: Snackdown 2019 is coming! There are two rounds (round A and round B) after the qualification round. From both of them, teams can qualify to the pre-elimination round. According to the rules, in each of these two rounds, teams are sorted in descending order by their score and each team with a score greater or equal to the score of the team at the  K = 1500 K = 1500 -th place advances to the pre-elimination round (this means it is possible to have more than  K K  qualified teams from each round in the case of one or more ties after the  K K -th place). Today, the organizers ask you to count the number of teams which would qualify for the pre-elimination round from round A for a given value of  K K  (possibly different from  1500 1500 ). They provided the scores of all teams to you; you should ensure that all teams scoring at least as many points as the...
Post a Comment
Read more

Chef and Typing CodeChef SnackDown 2021 Beginner Practice Contest

 Chef and Typing CodeChef SnackDown 2021 Beginner Practice Contest Question: Chef is practising his typing skills since his current typing speed is very low. He uses a training application that displays some words one by one for Chef to type. When typing a word, Chef takes 0.2 seconds to type the first character; for each other character of this word, he takes 0.2 seconds to type this character if it is written with a different hand than the previous character, or 0.4 seconds if it is written with the same hand. The time taken to type a word is the sum of times taken to type all of its characters. However, if a word has already appeared during practice, Chef can type it in half the time it took him to type this word for the first time. Currently, Chef is practising in easy mode, which only uses words that consists of characters 'd', 'f', 'j' and 'k'. The characters 'd' and 'f' are written using the left hand, while the characters 'j...
Post a Comment
Read more

Kitchen Timetable CodeChef SnackDown 2021 Beginner Practice Contest Solution

 Kitchen Timetable CodeChef SnackDown 2021 Beginner Practice Contest Solution Question: There are  N  students living in the dormitory of Berland State University. Each of them sometimes wants to use the kitchen, so the head of the dormitory came up with a timetable for kitchen's usage in order to avoid the conflicts: The first student starts to use the kitchen at the time  0  and should finish the cooking not later than at the time  A 1 . The second student starts to use the kitchen at the time  A 1  and should finish the cooking not later than at the time  A 2 . And so on. The  N -th student starts to use the kitchen at the time  A N-1  and should finish the cooking not later than at the time  A N The holidays in Berland are approaching, so today each of these  N  students wants to cook some pancakes. The  i -th student needs  B i  units of time to cook. The students have understood that probably...
Post a Comment
Read more

Chef and Operations CodeChef SnackDown 2021 Beginner Practice Contest

Chef and Operations CodeChef SnackDown 2021 Beginner Practice Contest Question: Chef has two sequences  A A  and  B B , each with length  N N . He can apply the following magic operation an arbitrary number of times (including zero): choose an index  i i  ( 1 ≤ i ≤ N − 2 1 ≤ i ≤ N − 2 ) and add  1 1  to  A i A i ,  2 2  to  A i + 1 A i + 1  and  3 3  to  A i + 2 A i + 2 , i.e. change  A i A i  to  A i + 1 A i + 1 ,  A i + 1 A i + 1  to  A i + 1 + 2 A i + 1 + 2  and  A i + 2 A i + 2  to  A i + 2 + 3 A i + 2 + 3 . Chef asks you to tell him if it is possible to obtain sequence  B B  from sequence  A A  this way. Help him! Input: The first line of the input contains a single integer  T  denoting the number of test cases. The description of  T  test cases follows. The first line of each test case contains a single integer...
Post a Comment
Read more

Round Robin Ranks CodeChef SnackDown 2021 Round 1A

 Round Robin Ranks CodeChef SnackDown 2021 Round 1A Question A round-robin tournament is being held in Chefland among N teams numbered 1,2,...,N. Every team play with all other teams exactly once. All games have only two possible results - win or loss. A win yields 2 points to the winning team while a loss yields no points. What is the maximum number of points a team finishing at the Kth position can score? Note: If two teams have the same points then the team with the higher team number achieves the better rank. Input Format First line will contain T, number of testcases. Then the testcases follow. Each testcase contains a single line of input, two space-separated integers N,K. Output Format For each testcase, output in a single line an integer - the maximum points the team ranked K in the round-robin tournament can score. Constraints 1≤T≤10^5 1≤K≤N≤10^9 Sample Input 1  3 3 3 4 1 7 4 Sample Output 1  2 6 8 Explanation Test Case 1: There are 3 teams in the tournament. The...
2 comments
Read more

Temple Land CodeChef SnacKDown 2021 Beginner Practice Contest

 Temple Land CodeChef SnacKDown 2021 Beginner Practice Contest Question: The snakes want to build a temple for Lord Cobra. There are multiple strips of land that they are looking at, but not all of them are suitable. They need the strip of land to resemble a coiled Cobra. You need to find out which strips do so. Formally, every strip of land, has a length. Suppose the length of the i-th strip is is  N i , then there will be  N i  integers,  H i1 , H i2 , .. H iN i , which represent the heights of the ground at various parts of the strip, in sequential order. That is, the strip has been divided into  N i  parts and the height of each part is given. This strip is valid, if and only if all these conditions are satisfied: There should be an unique 'centre' part. This is where the actual temple will be built. By centre, we mean that there should be an equal number of parts to the left of this part, and to the right of this part. H i1  = 1 The heights k...
Post a Comment
Read more

Delete Two Elements Educational Codeforces Round 115 Solution

 Delete Two Elements Educational Codeforces Round 115 Solution Introduction Educational Codeforces rounds are organized by Codeforces for the Division 2 Coders. Similarly Educational Codeforces Round was held on     Sunday, October 10, 2021 at 14:35 UTC+5.5   Series of Educational Rounds continue to be held as Harbour Space University initiative. This round will be rated for coders with rating upto 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the full correct solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution. You will be given 7 problems and two hours to solve them.  The contest was a success and lots of submissions were made by the hard striving coders. Problem A that is the Computer Game was very easy and had the maximum number of successful submission. Problem B was a not easy but not difficult also it was fit for an average coder to solve. Problem C although ...
Post a Comment
Read more

Unique Email Addresses LeetCode Solution

Unique Email Addresses LeetCode Solution   Question Every  valid email  consists of a  local name  and a  domain name , separated by the  '@'  sign. Besides lowercase letters, the email may contain one or more  '.'  or  '+' . For example, in  "alice@leetcode.com" ,  "alice"  is the  local name , and  "leetcode.com"  is the  domain name . If you add periods  '.'  between some characters in the  local name  part of an email address, mail sent there will be forwarded to the same address without dots in the local name. Note that this rule  does not apply  to  domain names . For example,  "alice.z@leetcode.com"  and  "alicez@leetcode.com"  forward to the same email address. If you add a plus  '+'  in the  local name , everything after the first plus sign  will be ignored . This allows certain emails to be filtered. Note that...
Post a Comment
Read more

Dance Moves CodeChef SnackDown 2021 Round 1A Solution

 Dance Moves CodeChef SnackDown 2021 Round 1A Solution Question This year Chef is participating in a Dancing competition. The dance performance will be done on a linear stage marked with integral positions. Initially, Chef is present at position X and Chef's dance partner is at position Y. Chef can perform two kinds of dance moves. If Chef is currently at position k, Chef can: Moonwalk to position k+2, or Slide to position k−1 Chef wants to find the minimum number of moves required to reach his partner. Can you help him find this number? Input Format First line will contain a single integer T, the number of testcases. Then the description of T testcases follows. Each testcase contains a single line with two space-separated integers X,Y, representing the initial positions of Chef and his dance partner, respectively. Output Format For each testcase, print in a separate line, a single integer, the minimum number of moves required by Chef to reach his dance partner. Constraints 1≤T≤10^...
Post a Comment
Read more