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.

Creating a NSItemProvider for custom model class (Drag & Drop API)

For a project that I will start working on this summers, I am thinking about implementing this feature where you can drag and drop one or multiple items on a view (circleView in this tutorial) and download all those items from the web. The idea of using drag and drop is nothing new in iOS and with iOS 11, Apple has introduced a specific API for users to do just this.

This API allows users to drag items within the app or from one app to another. On iPhones you can only drag the items within the app  while on iPad with the help of split view you can drag items from one app to another.

The drag and drop API is extremely easy to use and configuring it takes just few minutes. There are two separate protocols that deal with drag and drop. Also there is a UITableViewDragDelegate and UITableViewDropDelegate for dragging and dropping items between table views or within same table view.

NSItemProvider is a wrapper that creates a UIDragItem. Essentially, if you want to drag and drop items of type Strings, then you first have to wrap it with an itemProvider that will convert the data to NSString and create a UIDragItem. Then when you drop the item, it will convert it from NSString to String. Apple provides ItemProvider for types like UIImage, NSURL, NSString etc

If you are populating a table view with items of custom class then in order to drag and drop these items you have to use a custom NSItemProvider. In order to do this, you need to conform your model class to NSItemProviderReading, NSItemProviderWriting.

final class PodcastModelData: NSObject, Codable, NSItemProviderReading, NSItemProviderWriting {

Make sure to use NSObject and Codable. Codable protocol is a combination of two other protocols – Encodable & Decodable. We will use Codable to convert our object to JSON data and then when we drop it at the destination, it will revert back to the model class object.

final class PodcastModelData: NSObject, Codable, NSItemProviderReading, NSItemProviderWriting {
   
    
  // 1  
    var collectionName : String?
    var feedUrl: String?
    var artworkUrl100: String?
  // 2  
     init(collectionName: String, feedURL: String, artworkURL100: String) {
        self.collectionName = collectionName
        self.feedUrl = feedURL
        self.artworkUrl100 = artworkURL100
    }
   //3 
    static var writableTypeIdentifiersForItemProvider: [String] {
        return [(kUTTypeData) as String]
    }
    
// 4
    func loadData(withTypeIdentifier typeIdentifier: String, forItemProviderCompletionHandler completionHandler: @escaping (Data?, Error?) -> Void) -> Progress? {
        
        
        let progress = Progress(totalUnitCount: 100)
        // 5
        
        do {
            let encoder = JSONEncoder()
            encoder.outputFormatting = .prettyPrinted
            let data = try encoder.encode(self)
            let json = String(data: data, encoding: String.Encoding.utf8)
            progress.completedUnitCount = 100
            completionHandler(data, nil)
        } catch {
     
            completionHandler(nil, error)
        }
        
        return progress
    }

Let’s break down the above code:

  1. Class properties – three variables all of type of strings
  2.  simple initializer.
  3. First method to conform to –  ‘writableTypeIdentifiersForItemProvider‘ method returns an array of type of identifiers as Strings. Again it’s array so you can give them multiple identifiers but make sure that it’s in the order of precedence. We will be using KUTTypeData since we want to send our item as type Data.
  4. The second method to conform to –  in this method you will convert the  object to the type identifier which in our case is KUTTypeData. So we will be converting the object to JSON.
  5. We are simply encoding the class properties to JSON using JSONEncoder(). The progress variable keeps track of the loading / conversion.
  6. As soon as the loading is complete, the completion hander closure is called and the converted data is passed.

Now lets conform to NSItemProviderReading:

// 1
static var readableTypeIdentifiersForItemProvider: [String] {
        return [(kUTTypeData) as String]
    }
// 2
    static func object(withItemProviderData data: Data, typeIdentifier: String) throws -> PodcastModelData {
        let decoder = JSONDecoder()
        do {
            let myJSON = try decoder.decode(podcastModelData.self, from: data)
            return myJSON
        } catch {
            fatalError("Err")
        }
        
    }

Lets break down the above code:

  1. readableTypeIdentiferForItemProvider – again returning array of type identifiers in order of highest fidelity. In this case we are only returning KUTTypeData.
  2. This method creates a new instance of class with the given data and the identifier. In this method we will be using JSONDecoder() to decode the data back to instance of class (podcastModelData). The actual function returns ‘self’ however, it was giving me some issues so I added final infront of the class name and instead of ‘self‘ wrote the class name.

That’s it really! Now you it’s pretty straight forward to create UIDragItems with custom NSItemProvider.

func tableView(_ tableView: UITableView, itemsForBeginning session: UIDragSession, at indexPath: IndexPath) -> [UIDragItem] {
     
        let podcastItem = PodcastModelData(collectionName: collectionName, feedURL: feedUrl, artworkURL100: artworkUrl)
        
        let itemProvider = NSItemProvider(object: podcastItem)
        let dragItem = UIDragItem(itemProvider: itemProvider)
        return [dragItem]
    }

The NSitemProvider constructor requires the object of the class and not the class itself. In this case I am giving it podcastItem. The drag item constructor requires the itemProvider which we created earlier.

Since I am dropping all these elements on a custom circleView, therefore I am using UIDropInteractionDelegate and using this method:

   func dropInteraction(_ interaction: UIDropInteraction, performDrop session: UIDropSession) {
     session.loadObjects(ofClass: PodcastModelData.self) { (items) in
            if let podcasts = items as? [PodcastModelData] {
                //....
              //Do whatever you want to do with your dropped items here
            }
            
        }
      
    }

If you want to drop it on a table view then you have to use this function:

func tableView(_ tableView: UITableView, performDropWith coordinator: UITableViewDropCoordinator) { 
...
}

 

You can get the full source code for this project on my github here. Also check out the app in action here on my Twitter.

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