Finding the Length of the Longest Subarray with Distinct Elements in Swift

Swift: Longest subarray where all its elements are distinct

Introduction

When working with arrays, it's common to encounter problems that involve finding patterns or properties within subarrays. One such problem is finding the length of the longest subarray where all its elements are distinct. In this blog post, we'll discuss this problem and provide a Swift solution using a sliding window approach.

Problem Statement

Given an array of elements, we need to determine the length of the longest subarray where all its elements are distinct. For example, given the array [5, 1, 3, 5, 2, 3, 4, 1], the longest subarray of distinct elements is [5, 2, 3, 4, 1], and its length is 5.

Approach

To solve this problem efficiently, we can use a sliding window approach. We'll maintain two pointers: startIndex and endIndex, representing the start and end indices of the current subarray. Additionally, we'll use a dictionary, visitedElements, to store the index of each visited element.

Initialize startIndex and longestLength to 0.

Initialize an empty visitedElements dictionary.

Iterate through the array from left to right using the endIndex pointer.

Get the current element at array[endIndex].

If the current element is already present in visitedElements, indicating a duplicate, update startIndex to the maximum value between its current value and the index of the previous occurrence of the duplicate element plus one.

Update the index of the current element in visitedElements with endIndex.

Update longestLength with the maximum value between its current value and the length of the current subarray (endIndex - startIndex + 1).

Return longestLength as the result.

Swift Implementation

Here's the Swift implementation of the above approach:

func longestDistinctSubarrayLength(_ array: [Int]) -> Int {

var longestLength = 0

var startIndex = 0

var visitedElements = [Int: Int]() // Stores the index of each visited element

for endIndex in 0..<array.count {

let currentElement = array[endIndex]

if let previousIndex = visitedElements[currentElement] {

startIndex = max(startIndex, previousIndex + 1) // Update the start index to the next position after the duplicate element

}

visitedElements[currentElement] = endIndex // Update the index of the current element

longestLength = max(longestLength, endIndex - startIndex + 1)

}

return longestLength

}

Example Usage

Let's test the function with the example array [5, 1, 3, 5, 2, 3, 4, 1]:

let array = [5, 1, 3, 5, 2, 3, 4, 1]

let length = longestDistinctSubarrayLength(array)

print(length) // Output: 5

Explanation

In the example usage, the function longestDistinctSubarrayLength is called with the array [5, 1, 3, 5, 2, 3, 4, 1]. The function implements the sliding window approach to iterate through the array and find the longest subarray with distinct elements.

The function starts with startIndex and longestLength initialized to 0. It maintains a dictionary, visitedElements, to keep track of the indices of visited elements. The function iterates through the array using the endIndex pointer.

For each element, it checks if it has been visited before. If so, it updates startIndex to the next position after the previous occurrence of the duplicate element. The function then updates the index of the current element in visitedElements and updates longestLength with the maximum length found so far.

Finally, the function returns the length of the longest subarray with distinct elements.

Conclusion

In this blog post, we discussed the problem of finding the length of the longest subarray with distinct elements. We provided a Swift solution using the sliding window approach, which efficiently solves the problem in linear time complexity.

By leveraging the sliding window technique and the use of a dictionary to store visited elements, we can determine the length of the longest subarray with distinct elements in an optimal manner.

I hope this blog post has helped you understand the problem and its solution in Swift. Happy coding!

COFPROG