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?”