avatarjb stevenard

Free AI web copilot to create summaries, insights and extended knowledge, download it at here

2801

Abstract

"hljs-keyword">var</span> maxStack <span class="hljs-operator">=</span> <span class="hljs-type">Stack</span><<span class="hljs-type">T</span>>()</pre></div><p id="6bc7">2. Here is the push function, which pushes the new element into the standard stack, then find the new maximum from the previous maximum and the new element, pushes it to the max stack.</p><div id="8478"><pre><span class="hljs-keyword">func</span> <span class="hljs-title function_">push</span>(<span class="hljs-params">element</span>: <span class="hljs-type">T</span>) { stack.push(element) <span class="hljs-keyword">let</span> oldMax <span class="hljs-operator">=</span> maxStack.peek() <span class="hljs-operator">??</span> element <span class="hljs-keyword">let</span> newMax <span class="hljs-operator">=</span> <span class="hljs-built_in">max</span>(oldMax, element) maxStack.push(newMax) }</pre></div><p id="3ae5">3. Here is the pop function, which is popping the max stack and returning the result of popping the standard stack.</p><div id="c970"><pre><span class="hljs-keyword">func</span> <span class="hljs-title function_">pop</span>() -> <span class="hljs-type">T</span>? { <span class="hljs-keyword">_</span> <span class="hljs-operator">=</span> maxStack.pop() <span class="hljs-keyword">return</span> stack.pop() }</pre></div><p id="2441">4. Here is the get max function, which returns the top of the max stack.</p><div id="0f72"><pre><span class="hljs-keyword">func</span> <span class="hljs-title function_">getMax</span>() -> <span class="hljs-type">T</span>? { maxStack.peek() }</pre></div><p id="7aaa">5. Here is the empty computed property, which is checking if the standard stack is empty.</p><div id="c5da"><pre><span class="hljs-keyword">var</span> isEmpty: <span class="hljs-type">Bool</span> { stack.isEmpty() }</pre></div><h2 id="3a58">Complexity:</h2><p id="a25a">- Time Complexity: All functions run in a constant time O(1),</p><p id="00ab">- Space Complexity: The space complexity is still linear O(n), n being the number of elements pushed.</p><h2 id="4107">Test-cases:</h2><div id="3c95"><pre><span class="hljs-keyword">public</span> <span class="hljs-keyword">func</span> <span class="hljs-title function_">testMaxStack</span>() { <span class="hljs-keyword">let</span> maxStack <span class="hljs-operator">=</span> <span class="hljs-type">MaxStack</span><<span class="hljs-type">Int</span>>() <span class="hljs-built_in">assert</span>(maxStack.getMax() <span class="hljs-operator">==</span> <span class="hljs-literal">nil</span>,<span class="hljs-string">"mainMaxStack nil not equal"</span>) maxStack.push(element: <span class="hljs-number">1</span>) <span class="hljs-built_in">assert</span>(maxStack.getMax() <span class="hljs-operator">==</span> <span cla

Options

ss="hljs-number">1</span>,<span class="hljs-string">"mainMaxStack nil not equal"</span>)

maxStack.push(element: <span class="hljs-number">2</span>) <span class="hljs-built_in">assert</span>(maxStack.getMax() <span class="hljs-operator">==</span> <span class="hljs-number">2</span>,<span class="hljs-string">"mainMaxStack nil not equal"</span>)

maxStack.push(element: <span class="hljs-number">3</span>) <span class="hljs-built_in">assert</span>(maxStack.getMax() <span class="hljs-operator">==</span> <span class="hljs-number">3</span>,<span class="hljs-string">"mainMaxStack nil not equal"</span>) <span class="hljs-built_in">assert</span>(maxStack.pop() <span class="hljs-operator">==</span> <span class="hljs-number">3</span>,<span class="hljs-string">"mainMaxStack nil not equal"</span>) <span class="hljs-built_in">assert</span>(maxStack.getMax() <span class="hljs-operator">==</span> <span class="hljs-number">2</span>,<span class="hljs-string">"mainMaxStack nil not equal"</span>) <span class="hljs-built_in">assert</span>(maxStack.pop() <span class="hljs-operator">==</span> <span class="hljs-number">2</span>,<span class="hljs-string">"mainMaxStack nil not equal"</span>) <span class="hljs-built_in">assert</span>(maxStack.getMax() <span class="hljs-operator">==</span> <span class="hljs-number">1</span>,<span class="hljs-string">"mainMaxStack nil not equal"</span>) <span class="hljs-built_in">assert</span>(maxStack.pop() <span class="hljs-operator">==</span> <span class="hljs-number">1</span>,<span class="hljs-string">"mainMaxStack nil not equal"</span>) <span class="hljs-built_in">assert</span>(maxStack.getMax() <span class="hljs-operator">==</span> <span class="hljs-literal">nil</span>,<span class="hljs-string">"mainMaxStack nil not equal"</span>) }</pre></div><h2 id="5538">Follow-up:</h2><p id="9cbb">No follow-up question.</p><p id="4404"><a href="https://readmedium.com/algorithms-questions-429c4d84a98f"><< More Interview Questions</a> | <a href="https://readmedium.com/learn-data-structures-and-algorithms-with-swift-5-6-d9f36a4027dd">Data Structures and Algorythms >></a></p><div id="c879" class="link-block"> <a href="https://medium.com/@jbstevenard/membership"> <div> <div> <h2>Join Medium with my referral link — jb stevenard</h2> <div><h3>Read every story from jb stevenard (and thousands of other writers on Medium). Your membership fee directly supports jb…</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/0*TEb_Qg9xmrjfkxhH)"></div> </div> </div> </a> </div></article></body>

34. Max Stack

Question: You want to access the largest element in a stack in O(1).

Hints:

- You can store all local maximum.

Solution:

class MaxStack<T: Comparable> {
    // 1.
    fileprivate var stack = Stack<T>()
    fileprivate var maxStack = Stack<T>()

    // 2.
    func push(element: T) {
        stack.push(element)
        let oldMax = maxStack.peek() ?? element
        let newMax = max(oldMax, element)
        maxStack.push(newMax)
    }

    // 3.
    func pop() -> T? {
        _ = maxStack.pop()
        return stack.pop()
    }

    // 4.
    func getMax() -> T? {
        maxStack.peek()
    }

    // 5.
    var isEmpty: Bool {
        stack.isEmpty()
    }
}

Explanations:

1. For the max stack, we need two stacks, one to pile up all elements and one to keep the local maximum.

fileprivate var stack = Stack<T>()
fileprivate var maxStack = Stack<T>()

2. Here is the push function, which pushes the new element into the standard stack, then find the new maximum from the previous maximum and the new element, pushes it to the max stack.

func push(element: T) {
  stack.push(element)
  let oldMax = maxStack.peek() ?? element
  let newMax = max(oldMax, element)
  maxStack.push(newMax)
}

3. Here is the pop function, which is popping the max stack and returning the result of popping the standard stack.

func pop() -> T? {
  _ = maxStack.pop()
  return stack.pop()
}

4. Here is the get max function, which returns the top of the max stack.

func getMax() -> T? {
  maxStack.peek()
}

5. Here is the empty computed property, which is checking if the standard stack is empty.

var isEmpty: Bool {
  stack.isEmpty()
}

Complexity:

- Time Complexity: All functions run in a constant time O(1),

- Space Complexity: The space complexity is still linear O(n), n being the number of elements pushed.

Test-cases:

public func testMaxStack() {
  let maxStack = MaxStack<Int>()
  assert(maxStack.getMax() == nil,"mainMaxStack nil not equal")
  maxStack.push(element: 1)
  assert(maxStack.getMax() == 1,"mainMaxStack nil not equal")

  maxStack.push(element: 2)
  assert(maxStack.getMax() == 2,"mainMaxStack nil not equal")

  maxStack.push(element: 3)
  assert(maxStack.getMax() == 3,"mainMaxStack nil not equal")
  assert(maxStack.pop() == 3,"mainMaxStack nil not equal")
  assert(maxStack.getMax() == 2,"mainMaxStack nil not equal")
  assert(maxStack.pop() == 2,"mainMaxStack nil not equal")
  assert(maxStack.getMax() == 1,"mainMaxStack nil not equal")
  assert(maxStack.pop() == 1,"mainMaxStack nil not equal")
  assert(maxStack.getMax() == nil,"mainMaxStack nil not equal")
}

Follow-up:

No follow-up question.

<< More Interview Questions | Data Structures and Algorythms >>

Data Structures
Algorithms
Coding
Interview Questions
Programming
Recommended from ReadMedium