Home » Technical Interview Questions » Stack Interview Questions » Form Minimum Number From Given Sequence

Form Minimum Number From Given Sequence



Frequently asked in Amazon
Array Goldman Sachs Stack String

Problem Statement

The problem “Form Minimum Number From Given Sequence states that you are given a string s of length/size n representing a pattern of characters ‘I’ i.e. increasing and ‘D’ i.e. decreasing only. Print the minimum number for the given pattern with unique digits from 1-9.

For instance –

Form Minimum Number From Given Sequence

Example

s = "DD"
3 2 1

Explanation: Since the digits can’t be negative, we will select 3 as the first digit and then keep on decrementing the upcoming digits.

s = "DIDI"
2 1 4 3 5

Method 1

Algorithm

  1. Initialize a string s.
  2. Traverse through the given string s and check if the current character in the string is equal to ‘I’, calculate the total number of next consecutive characters equal to ‘D’ in the given string.
  3. If the character ‘I’ is the first character in the string, print the increasing pattern starting from 1 else print the next digit.
  4. Print the decreasing pattern for all the next consecutive characters equal to ‘D’ in the given string.
  5. Similarly, check if the current character in the string is equal to ‘D’, check if the character ‘D’ is the first character in the string, count all the ‘D’s in the string and print the pattern accordingly.
  6. Else decrement the last entry by 1.

Complexity Analysis

Time Complexity

O(n) where n is the length of the given string s.

Space Complexity

O(n) because we used space to store the characters of the given string.

Code

C++ Program to form minimum number from given sequence

#include <bits/stdc++.h> 
using namespace std; 
  
void FormMinNumber(string arr){ 
    int curr_max = 0; 
  
    int last_entry = 0; 
  
    int j; 
  
    for(int i=0; i<arr.length(); i++){ 
        int noOfNextD = 0; 
  
        switch(arr[i]){ 
            case 'I': 
                j = i+1; 
                while (arr[j] == 'D' && j < arr.length()){ 
                    noOfNextD++; 
                    j++; 
                } 
                    
                if (i==0){ 
                    curr_max = noOfNextD + 2; 
      
                    cout << " " << ++last_entry; 
                    cout << " " << curr_max; 
      
                    last_entry = curr_max; 
                } 
                
                else{ 
                    curr_max = curr_max + noOfNextD + 1; 
      
                    last_entry = curr_max; 
                    cout << " " << last_entry; 
                } 
      
                for (int k=0; k<noOfNextD; k++){ 
                    cout << " " << --last_entry; 
                    i++; 
                } 
                break; 
      
            case 'D': 
                if (i == 0){ 
                    j = i+1; 
                    while (arr[j] == 'D' && j < arr.length()){ 
                        noOfNextD++; 
                        j++; 
                    } 
      
                    curr_max = noOfNextD + 2; 
      
                    cout << " " << curr_max << " " << curr_max - 1; 
      
                    last_entry = curr_max - 1; 
                } 
                
                else{ 
                    cout << " " << last_entry - 1; 
                    last_entry--; 
                } 
                break; 
        } 
    } 
    cout << endl; 
} 
  
int main(){ 
    string s = "IDID";
    
    FormMinNumber(s); 
    
    return 0; 
}
1 3 2 5 4

Java Program to form minimum number from given sequence

class MinNum{ 
      
    static void FormMinNumber(String arr){ 
        int curr_max = 0; 
  
        int last_entry = 0; 
  
        int j; 
  
        for (int i = 0; i < arr.length(); i++){ 
            int noOfNextD = 0; 
  
            switch (arr.charAt(i)){ 
                case 'I': 
                    j = i + 1; 
                    while (j < arr.length() && arr.charAt(j) == 'D'){ 
                        noOfNextD++; 
                        j++; 
                    } 
  
                    if (i == 0){ 
                        curr_max = noOfNextD + 2; 
  
                        System.out.print(" " + ++last_entry); 
                        System.out.print(" " + curr_max); 
  
                        last_entry = curr_max; 
                    }  
                    
                    else{ 
                        curr_max = curr_max + noOfNextD + 1; 
  
                        last_entry = curr_max; 
                        System.out.print(" " + last_entry); 
                    } 
  
                    for (int k = 0; k < noOfNextD; k++){ 
                        System.out.print(" " + --last_entry); 
                        i++; 
                    } 
                    break; 
  
                case 'D': 
                    if (i == 0){ 
                        j = i + 1; 
                        while (j < arr.length()&&arr.charAt(j) == 'D'){ 
                            noOfNextD++; 
                            j++; 
                        } 
  
                        curr_max = noOfNextD + 2; 
  
                        System.out.print(" " + curr_max + " " + (curr_max - 1)); 
  
                        last_entry = curr_max - 1; 
                    }  
                    else{ 
                        System.out.print(" " + (last_entry - 1)); 
                        last_entry--; 
                    } 
                    break; 
            } 
        } 
        System.out.println(); 
    } 
  
    public static void main(String[] args){ 
        String s = "IDID";
        FormMinNumber(s); 
    } 
}
1 3 2 5 4

Method 2

Algorithm

  1. Initialize a string s.
  2. Create a vector v of type integer.
  3. Check if the first character of the given string is ‘I’, push 1 and 2 in the vector and set the minimum available number as 3 and position of ‘I’ as 1.
  4. Else push 2 and 1 in the vector and set the minimum available number as 3 and position of ‘I’ as 0.
  5. Traverse through the string starting from 1 and check if the current character of the given string is ‘I’, push the minimum available number in the vector, increment the minimum available number and update the position of ‘I’ as current index + 1.
  6. Else push the current element in vector in vector again and increment the minimum available number.
  7. Print the vector.
READ  Iterative method to find ancestors of a given binary tree

Complexity Analysis

Time Complexity

O(n) where n is the length of the given string s.

Space Complexity

O(n) because we used space to store the characters of the given string.

Code

C++ Program to form minimum number from given sequence

#include <bits/stdc++.h> 
using namespace std; 
  
void FormMinNumber(string arr){ 
    int min_avail = 1, pos_of_I = 0; 
  
    vector<int>v; 
  
    if (arr[0]=='I'){ 
        v.push_back(1); 
        v.push_back(2); 
        min_avail = 3; 
        pos_of_I = 1; 
    } 
    
    else{ 
        v.push_back(2); 
        v.push_back(1); 
        min_avail = 3; 
        pos_of_I = 0; 
    } 
  
    for (int i=1; i<arr.length(); i++){ 
        if (arr[i]=='I'){ 
            v.push_back(min_avail); 
            min_avail++; 
            pos_of_I = i+1; 
        } 
        
        else{ 
            v.push_back(v[i]); 
            for (int j=pos_of_I; j<=i; j++){ 
                v[j]++; 
            }
  
            min_avail++; 
        } 
    } 
  
    for (int i=0; i<v.size(); i++){ 
        cout << v[i] << " "; 
    }
    cout << endl; 
} 
  
int main(){ 
    string s = "IDID";
    
    FormMinNumber(s); 
    
    return 0; 
}
1 3 2 5 4

Java Program to form minimum number from given sequence

import java.util.*; 

class MinNum{ 
      
    static void FormMinNumber(String arr){ 
        int min_avail = 1, pos_of_I = 0;  
        
        ArrayList<Integer> al = new ArrayList<>(); 
        
        if (arr.charAt(0) == 'I'){  
            al.add(1);  
            al.add(2);  
            min_avail = 3;  
            pos_of_I = 1;  
        }  
        
        else{ 
            al.add(2); 
            al.add(1); 
            min_avail = 3;  
            pos_of_I = 0;  
        } 
        
        for (int i = 1; i < arr.length(); i++){ 
            if (arr.charAt(i) == 'I'){ 
                al.add(min_avail); 
                min_avail++; 
                pos_of_I = i + 1; 
            } 
            
            else{ 
                al.add(al.get(i)); 
                for (int j = pos_of_I; j <= i; j++) {
                    al.set(j, al.get(j) + 1); 
                }
                min_avail++; 
            } 
        } 
        
        for (int i = 0; i < al.size(); i++) {
            System.out.print(al.get(i) + " "); 
        }
        System.out.println();  
    } 
  
    public static void main(String[] args){ 
        String s = "IDID";
        FormMinNumber(s); 
    } 
}
1 3 2 5 4

Method 3

Algorithm

  1. Initialize a string s.
  2. Create a stack data structure.
  3. Traverse through the string and push the current index + 1 in the stack at every iteration. Chcek if the current index is equal to the length of the string or the current character in the string is equal to ‘I’, while the stack is not empty concatenate all the elements of the stack in a string.
  4. Print the string.
READ  Check for Balanced Parentheses in an Expression

Complexity Analysis

Time Complexity

O(n) where n is the length of the given string s.

Space Complexity

O(n) because we used space to store the characters of the given string.

Code

C++ Program to form minimum number from given sequence

#include <bits/stdc++.h> 
using namespace std; 
  
void FormMinNumber(string arr){ 
    string result; 
  
    stack<int> stk; 
  
    for (int i = 0; i <= arr.length(); i++){ 
        stk.push(i + 1); 
  
        if (i == arr.length() || arr[i] == 'I'){ 
            
            while (!stk.empty()){ 
                result += to_string(stk.top()); 
                result += " "; 
                stk.pop(); 
            } 
        } 
    } 
  
    cout << result << endl;  
} 
  
int main(){ 
    string s = "IDID";
    
    FormMinNumber(s); 
    
    return 0; 
}
1 3 2 5 4

Java Program to form minimum number from given sequence

import java.util.*; 

class MinNum{ 
      
    static void FormMinNumber(String arr){ 
        String result = ""; 
  
        Stack<Integer> stk = new Stack<Integer>(); 
  
        for (int i = 0; i <= arr.length(); i++) { 
            stk.push(i + 1); 
  
            if (i == arr.length() || arr.charAt(i) == 'I') { 
                while (!stk.empty()) { 
                    result += String.valueOf(stk.peek()); 
                    result += " "; 
                    stk.pop(); 
                } 
            } 
        } 
  
        System.out.println(result);   
    } 
  
    public static void main(String[] args){ 
        String s = "IDID";
        FormMinNumber(s); 
    } 
}
1 3 2 5 4

Method 4

Algorithm

  1. Initialize a string s.
  2. Check if the length of the given string is greater than or equal to 9, print -1, and return.
  3. Traverse through the given string and check if the current index is equal to the length of the string or the current character in the string is equal to ‘I’, Traverse again from the current index – 1 to 0 and update the result of current index + 1.
  4. If the current index is greater than or equal to 0 and the current character in the string is equal to ‘I’, break the loop.
  5. Print result.

Complexity Analysis

Time Complexity

O(n) where n is the length of the given string s.

READ  Implement a stack using single queue

Space Complexity

O(n) because we used space to store the characters of the given string.

Code

C++ Program to form minimum number from given sequence

#include <bits/stdc++.h> 
using namespace std; 
  
string FormMinNumber(string arr){ 
    int n = arr.length(); 
  
    if(n >= 9){ 
        return "-1";
    }
  
    string result(n+1, ' ');  
  
    int count = 1;   
  
    for (int i = 0; i <= n; i++){
        
        if (i == n || arr[i] == 'I'){
            
            for (int j = i - 1 ; j >= -1 ; j--){ 
                result[j + 1] = '0' + count++; 
                
                if(j >= 0 && arr[j] == 'I'){ 
                    break; 
                }
            } 
        } 
    } 
    return result;   
} 
  
int main(){ 
    string s = "IDID";
    
    cout<<FormMinNumber(s); 
    
    return 0; 
}
13254

Java Program to form minimum number from given sequence

import java.util.*; 

class MinNum{ 
      
    static String FormMinNumber(String arr){ 
        int n = arr.length(); 
  
        if (n >= 9){ 
            return "-1";
        }
  
        char result[] = new char[n + 1]; 
  
        int count = 1; 
  
        for (int i = 0; i <= n; i++){ 
            
            if (i == n || arr.charAt(i) == 'I'){ 
                
                for (int j = i - 1; j >= -1; j--){ 
                    result[j + 1] = (char) ((int) '0' + count++); 
                    
                    if (j >= 0 && arr.charAt(j) == 'I'){ 
                        break; 
                    }
                } 
            } 
        } 
        return new String(result);   
    } 
  
    public static void main(String[] args){ 
        String s = "IDID";
        System.out.println(FormMinNumber(s)); 
    } 
}
13254
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup