Solving Min Stack Problem using Swift

It’s been a while since I last posted an article on an algorithm and data structure problem. This time I decided to solve the Min Stack problem. In Min Stack you need to find the minimum element inside a stack in constant time. An alternate question is Max Stack where you have to find the maximum element in a stack. Both are pretty similar conceptually.

The problem explicitly states that each stack method should run at constant time – O(1).

This is the problem statement:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • getMin() — Retrieve the minimum element in the stack.

 

Before continuing, make sure you try this problem yourself.

We will create a class calling it MinStack and inside it we will have two arrays.

private var elements: [Int] = []
private var minElements: [Int] = []

The elements array will be our main stack where the user appends or pushes new elements into. The minElement array is going to act as a secondary stack which will be used to keep track of the minimum element value at different stages.

Let’s code the first method – push(x):

func push(_ x: Int) {
        elements.append(x)
        if minElements.count == 0 {
            minElements.append(x)
        }else {
            if let minElement = minElements.last, let lastElement = elements.last {
                if lastElement <= minElement {
                    minElements.append(lastElement)
                }
            }
        }
    }

In this method, we are appending or pushing the element passed in by the function argument to the main ‘elements’ array. Then if the minElements array is empty we are simply appending the passed element into it. This is to “warm up” both stacks.

The next time the user pushes an element, we will simply append it in the elements array however, we will apply some bit of logic before appending it to the minElements stack.

We are using last() method which comes by default with Array. This method returns the last element in the array. The element type returned is optional (if array is empty, nil will be returned). Therefore, we are safely unwrapping last elements from both arrays using If – let statements.

Once we get the elements, we are checking if the top element in the element stack is less than or equal to the top element in the minElement stack. If it is, that element is appended or pushed to minElements stack as well.

Next, let’s implement pop() method:

In this method we will be removing the top element in the stack. We will use the .popLast() method. This method removes the last element in the array and also returns that element.

func pop() {
        let popElement = elements.popLast()
        if let poppedElement = popElement, let minElementPop = minElements.last {
            if poppedElement == minElementPop {
                minElements.popLast()
            }
        }
    }

We grab the returned last element from the main elements stack, and then again check the top element of minElements stack and check if the popped element and the top element of minElements stack is equal or not. If they are equal, then the top element is removed from minElements stack as well.

The remaining two methods are top() and getMin() – in both these methods we are simply popping the last element in the arrays and returning them.

    func top() -> Int {
        return elements.last ?? 0
    }
    
    func getMin() -> Int {
        return minElements.last ?? 0
    }

The main thing here to notice is that the methods run at constant time. Nowhere inside any method did we iterated through the entire array – (this will be O(n)). With O(1) time complexity our algorithm works at constant time and not dependent to the size of the stack.

Solving longest consecutive sequence in an array using Swift

This question is asked quite often in technical interview . The problem is this:

Write a function that takes in an unsorted array of integers and returns the longest range or longest consecutive sequence. For example:

let array = [3,2,4,5,6,7,12,10,8,9,21,15,11,13,16,19,20,19]

In this array there are 18 elements, however the longest consecutive goes from 2 to 13. You can simply eye ball the above array and see consecutive numbers from 2 all the way till 13. Then you have another range from 19 to 21 and another even smaller one that goes from 15 to 16.

The function should return the start and end values of the sequence.

I strongly urge to first try this problem out before checking out my version of this solution given below.

Alright, now let’s dive in to the solution. In my version of this solution, I am using only one Hash Map or Dictionary.The dictionary is of type [Int : Bool]. When we have used an integer successfully in creating a sequence the bool value should become true.

Here is the function signature:

func findLongestRange(in array: [Int]) -> String {

Here I am initializing the dictionary and three variables to keep track of the longest sequence and in the for loop, I am giving value of false to all the entries of the dictionary.

 var numbersDic = [Int: Bool]()
      
        
        var longestSequence = 0
        var recordInitialNumber = 0
        var recordLastNumber = 0
        
        if array.count <  1 {
            return "No Sequence Found"
        }
      
        // Adding the numbers as keys with Bool as the value in the dictionary
        for n in array {
            numbersDic[n] = false
        }
      
for n in array {
           
            if ( numbersDic[n]! ) {
                continue
            }
            var previousVal = n - 1
            var nextVal = n + 1
            
            numbersDic[n] = true
            
            while numbersDic[previousVal] != nil {
                numbersDic[previousVal] = true
                previousVal = previousVal - 1
            }
            
            
             //Checking if a next value is available
            while numbersDic[nextVal] != nil {
                numbersDic[nextVal] = true
                nextVal = nextVal + 1
            }

This is the meat of the code. In this part, we are essentially first checking if the number we have landed on is already used in some other sequence by checking its value. If its true, we continue with the next iteration of the loop otherwise we continue. Then we are are setting previousVal and nextValue as current value (n) – 1 and current value + 1 respectively.
By using two while loops, we are first looking for the previous value to the current number in the hash map. If the value for it exists or the key is available, the bool value is switched to true. If there is no value in the dictionary for the previousVal key the while loop ends and goes to the next loop where we check the next value in the loop. Again the same thing, adding 1 to the nextVal and checking its presence in the hash map.

Then at the end we are checking if the current two values of nextValue and previousValue has the highest amount of numbers between them by taking the difference and returning a string:

//Checking longest sequence
            
            let difference =  (nextVal - 1) - (previousVal + 1)
           
            if (difference > longestSequence) {
                longestSequence = difference
                recordInitialNumber = previousVal + 1
                recordLastNumber = nextVal - 1
                
            } 
          return "The longest sequence starts at \(recordInitialNumber) and ends at  \(recordLastNumber)"

This is the output you get when you run this code:

The Longest sequence starts at 2 and ends at 13

Checking this algorithm in leetcode returns this result:

 

Solving 3SUM problem using Swift

The 3Sum problem is often asked during technical interviews and the problem at first seems quite tough but it’s got a pretty similar taste to 2Sum problem.

Here is the problem: You are given a sorted array, and you need to find three numbers in the array that can add up to a particular sum which is also given to you.

I would strongly urge everyone to first try solving the 2Sum problem where it requires you to find 2 numbers that add up to give you the given sum and similarly practice this problem before continuing to the solution given below. 

So first lets start with function signature:

func threeSumProblem(for array: [Int], sum: Int) -> Bool

The function takes in the sorted array of type Int and a Sum integer and returns a Bool.

func threeSumProblem(for array: [Int], sum: Int) -> Bool
    {
        var complement = 0
        var lowIndex = 0
        var highIndex = array.count - 1

Firstly, I am initializing three variables – complement, lowIndex & highIndex. To solve the 3Sum problem here is the method I am using:  If the array is say [1,4,6,4] and sum is 11, then we will first hold on to first number which in this case is 1, and then using linear pointer method on the remaining array [4,6,4]. Here we will have a pointer which will start from 4 with one index more than the number we holding on to, and the high pointer will start with index of array.count – 1. (The right hand side)

for (index, element) in array.enumerated() {
            lowIndex = index + 1
            complement = sum - element
            while (lowIndex < highIndex) 
                { if (array[lowIndex] + array[highIndex] > complement ) {
                    highIndex -= 1
                }else if (array[lowIndex] + array[highIndex] < complement) {
                    lowIndex += 1
                }else {
                    print(element, array[lowIndex], array[highIndex])
                    return true
                }
            }
            
             lowIndex = 0
             highIndex = array.count - 1
           
        }

Next, we will start a for loop which will give us the element and the index of that element in the sequence, hence using array.enumerated() . Then inside the for loop, I am setting lowIndex to current index + 1. We also set complement by subtracting the current element we are on with the sum passed in the function by the user.

Then we have another loop inside this for loop. This time it’s a while loop. The while loop will keep running until the two pointers cross over.

Inside the while loop, we have three if statements:

 if (array[lowIndex] + array[highIndex] > complement ) {
                    highIndex -= 1
                }else if (array[lowIndex] + array[highIndex] < complement) {
                    lowIndex += 1
                }else {
                    print(element, array[lowIndex], array[highIndex])
                    return true
                }

Now the problem has been converted in to 2sum. We will check if the two numbers sum is greater than complement, if yes, then move the highIndex pointer by 1 to the left. Similarly, if the sum of two numbers is less than the complement, then move the lowIndex pointer by 1 to the right. Else, if the sum of two numbers is equal to complement, then return true.

After this if statement, we are setting the lowIndex and highIndex back to 0 and array.count – 1.

Next call this function:

let array = [4,3,5,1,5]
print(threeSumProblem(for: array, sum: 14))

The output for this is:

//output
4 5 5
true

This is how you can solve this algorithm. This particular solution is O(n^2) mainly as we are using two nested loops.

Interview Question: How to solve the recurrent value problem?

So I was reading an article where the person was talking about the internship interview process and in it, the person was asked 2 algorithm related questions. I decided to solve them myself and see how I would approach such a problem.

Here is the problem — you are given an array of integers [1,2,1,3,3] and you want to find:

    1. The first consecutive recurring number. Then answer of this will be 3.
    2. The first recurring number in the array. The answer of this will be 1.

Continue reading “Interview Question: How to solve the recurrent value problem?”