Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • EspaΓ±ol

β€ΊProblems: Stacks & Queues

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Sort Stack

Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array).The stack supports the following operations: push, pop, peek, and isEmpty

πŸ‘‰ Link here to the repo to solve the problem

imagen

Hints: #15, #32, #43

πŸ‘Œ Tips

One way of sorting an array is to iterate through the array and insert each element into a new array in sorted order. Can you do this with a stack?

Imagine your secondary stack is sorted. Can you insert elements into it in sorted order? You might need some extra storage. What could you use for extra storage?

Keep the secondary stack in sorted order, with the biggest elements on the top. Use the primary stack for additional storage.

πŸ‘Š Solution 1

This approach utilises multiple stacks to keep track of every insert we do. We want to have a stack of numbers that are smaller than the one we are inserting and one with bigger than.

Once we have this we can repopulate the main stack in this order: bigger > inserted number > smaller than. This way the smaller number will always be at the top of the stack, sorting occurs at insertion.

public class SortStack {
    private static Stack<Integer> stack = new Stack<>();


    public void push(int i) {
        if (stack.isEmpty()) stack.push(i);
        else {
            Stack<Integer> biggerThan = new Stack<>();
            Stack<Integer> smallerThan = new Stack<>();

            while (!stack.isEmpty()) {
                Integer n = stack.pop();
                if (n >= i) biggerThan.push(n);
                else smallerThan.push(n);
            }

            while (!biggerThan.isEmpty()) {
                stack.push(biggerThan.pop());
            }

            stack.push(i);

            while (!smallerThan.isEmpty()) {
                stack.push(smallerThan.pop());
            }


        }
    }

    public int pop() {
        return stack.pop();
    }

    public int peek() {
        return stack.peek();
    }

    public boolean isEmpty() {
        return this.stack.isEmpty();
    }
}
Last updated on 3/10/2020
← Queue via StacksAnimal Shelter β†’
  • πŸ‘‰ Link here to the repo to solve the problem
  • πŸ‘Œ Tips
  • πŸ‘Š Solution 1
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright Β© 2021 Kodr