iOS Interview - Sliding Window Technique

April 12, 20247 min read#swift, #interview, #leetcode

The sliding window technique is a powerful approach that can help solve a wide range of problems efficiently. This technique is particularly useful when dealing with arrays, strings, or other sequential data structures where you need to process a subset of elements at a time.

Understanding the Sliding Window Technique

The sliding window technique involves maintaining a window of elements from the input data structure and adjusting the window’s boundaries as we progress through the data. The window can be of fixed size or variable size, depending on the problem at hand. By sliding the window over the data, we can efficiently process the elements within the window and extract meaningful information.

The sliding window technique is often used to solve problems that involve finding subarrays or substrings that satisfy certain conditions. Instead of naively iterating through all possible subarrays or substrings, which can lead to quadratic time complexity, the sliding window technique allows us to solve such problems in linear time complexity.

Problem 1: Maximum Sum Subarray of Size K

Let’s consider a problem where we need to find the maximum sum subarray of a fixed size K within a given array of integers. We can efficiently solve this problem using the sliding window technique. Here’s an example implementation in Swift:

  * Time Complexity: O(n), Space Complexity: O(1)
func maxSumSubarray(arr: [Int], k: Int) -> Int {
    var maxSum = Int.min
    var windowSum = 0
    var windowStart = 0

    for windowEnd in 0..<arr.count {
        windowSum += arr[windowEnd]

        if windowEnd >= k - 1 {
            maxSum = max(maxSum, windowSum)
            windowSum -= arr[windowStart]
            windowStart += 1

    return maxSum

// Example usage
print(maxSumSubarray(arr: [1, 4, 2, 10, 23, 3, 1, 0, 20], k: 4)) // 39
print(maxSumSubarray(arr: [2, 1, 5, 1, 3, 2], k: 3)) // 9
print(maxSumSubarray(arr: [2, 3, 4, 1, 5], k: 2)) // 7

In this example, we define a function maxSumSubarray that takes an array arr and the size of the subarray k as input. We initialize variables to keep track of the maximum sum (maxSum), the current window sum (windowSum), and the starting index of the window (windowStart).

We then iterate through the array using the windowEnd variable. At each iteration, we add the current element to the windowSum. Once the window size reaches k, we update the maxSum if necessary by comparing it with the current windowSum. We then slide the window by subtracting the element at windowStart from the windowSum and incrementing windowStart.

By the end of the iteration, maxSum will hold the maximum sum of any subarray of size k within the given array.

We are using a fixed size sliding window to solve this problem.

Problem 2: Longest Substring Without Repeating Characters

Leetcode Problem: Longest Substring Without Repeating Characters

public class Problem {

    public init() {}

     * Primary idea: Use a dictionary to hold the next possible valid position of characters of the non-repeating substring,
     *               and then iterate the string to update maxLen, dictionary, and startIdx encountering duplicates
     * Time Complexity: O(n), Space Complexity: O(n)
    public func lengthOfLongestSubstring(_ s: String) -> Int {
        // Max possible length of non-repeating string
        var maxLen = 0

        // starting the initial point of window to index 0
        var startIdx = 0

        // Dictionary with key = character, and value = index of the next possible valid position of the character in a non-repeating string
        var charToPos = [Character: Int]()

        // Convert the string into array of characters for processing
        let characters = Array(s)

        // Integrate through every character of the string
        for (i, character) in characters.enumerated() {
            // Checking if we have already seen the element or not
            if let pos = charToPos[character] {
                // If we have seen the character, move the start pointer
                // to position after the last occurrence
                startIdx = max(startIdx, pos + 1)

            // Updating the last seen value of the character
            charToPos[character] = i

            // Comparing the stored maxLen with the length of the last substring
            maxLen = max(maxLen, i - startIdx + 1)

        return maxLen

private let solution = Problem()
var s1 = "abcabcbb"
print(solution.lengthOfLongestSubstring(s1)) // 3
var s2 = "bbbbb"
print(solution.lengthOfLongestSubstring(s2)) // 1
var s3 = "pwwkew"
print(solution.lengthOfLongestSubstring(s3)) // 3

We are using a variable size sliding window to solve this problem.

Problem 3:

Find All Anagrams in a String

  * Time Complexity: O(n), Space Complexity: O(n)
class Solution {
    func findAnagrams(_ s: String, _ p: String) -> [Int] {
        let countP = p.count

        // Convert the strings to arrays of characters
        let s = Array(s)
        let p = Array(p)

        // Array to store the frequency of occurences of a character in String S and P
        var arrP = Array(repeating: 0, count: 26)
        var arrS = Array(repeating: 0, count: 26)

        // Arrat to store the result
        var resultArr: [Int] = []

        // Update the occurences of every character in P.
        for char in p {
          arrP[char.indexAsciiValue] += 1

        // Starting with left pointer at 0
        var left = 0

        // Move the right pointer to the right in every looping step
        for (right, value) in s.enumerated() {
            arrS[value.indexAsciiValue] += 1

            // Check if the length of the sliding window = length of string P
            if right - left + 1 == countP {
                if arrP == arrS { // compare the frequency of occurences of 2 arrays. If they are equal => Store the result

                // Reset the occurency of the character at the left pointer
                // Then move the left point of the window one step forward
                arrS[s[left].indexAsciiValue] -= 1
                left += 1

        return resultArr

extension Character {
    var indexAsciiValue: Int {
        Int(self.asciiValue! - Character("a").asciiValue!)

Further Reading

Quick Drop logo

Profile picture

Personal blog by An Tran. I'm focusing on creating useful apps.
#Swift #Kotlin #Mobile #MachineLearning #Minimalist

© An Tran - 2024