Generic subscripts in Swift - Time & Space Complexity

Time Complexity: Generic subscripts

O(1)

Understanding Time Complexity

When using generic subscripts in Swift, it's important to know how the time to access elements changes as the data grows.

We want to find out how the number of steps grows when we use a generic subscript to get or set values.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Box {
    private var storage: [String: Any] = [:]

    subscript(key: String) -> T? {
        get { storage[key] as? T }
        set { storage[key] = newValue }
    }
}

var box = Box()
let value: Int? = box["age"]
    

This code defines a generic subscript to get or set values of any type stored in a dictionary by key.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Dictionary lookup by key inside the subscript.
• How many times: Once per subscript access.

How Execution Grows With Input

Looking up a key in a dictionary usually takes about the same time no matter how many items are stored.

Input Size (n)	Approx. Operations
10	About 1 lookup step
100	About 1 lookup step
1000	About 1 lookup step

Pattern observation: The time to access a value stays roughly the same even as the dictionary grows larger.

Final Time Complexity

Time Complexity: O(1)

This means accessing or setting a value with a generic subscript takes about the same time no matter how many items are stored.

Common Mistake

[X] Wrong: "Using a generic subscript makes access slower as the dictionary grows because it has to check types each time."

[OK] Correct: The type check happens only once after the fast dictionary lookup, so it does not slow down with more items.

Interview Connect

Understanding how generic subscripts work and their time cost shows you can reason about flexible code without losing performance.

Self-Check

"What if the storage used an array of key-value pairs instead of a dictionary? How would the time complexity change?"

Practice

1. What is the main benefit of using generic subscripts in Swift?

easy

A. They allow subscripts to accept different types as keys or indexes.

B. They make subscripts run faster by using fixed types only.

C. They restrict subscripts to only integer indexes.

D. They automatically convert all keys to strings.

Solution

1. Step 1: Understand generic subscripts purpose

   Generic subscripts let you write one subscript that works with many types of keys or indexes.

2. Step 2: Compare options with this purpose

   Only They allow subscripts to accept different types as keys or indexes. correctly states that generic subscripts accept different types as keys or indexes.

3. Final Answer:

   They allow subscripts to accept different types as keys or indexes. -> Option A

4. Quick Check:

   Generic subscripts = flexible key types [OK]

Hint: Generic subscripts = flexible keys/indexes [OK]

Common Mistakes:

• Thinking generic subscripts improve speed
• Assuming subscripts only accept integers
• Believing keys auto-convert to strings

2. Which of the following is the correct syntax to declare a generic subscript in Swift?

easy

A. subscript(index: T) -> String { get }

B. func subscript<T>(index: T) -> String { get }

C. subscript<T>(index: Int) -> T { get }

D. subscript<T>(index: T) -> String { get }

Solution

1. Step 1: Recall generic subscript syntax

   Generic subscripts use subscript<T>(index: T) -> ReturnType syntax.

2. Step 2: Check each option

   subscript<T>(index: T) -> String { get } matches the correct syntax. func subscript<T>(index: T) -> String { get } wrongly uses func. subscript(index: T) -> String { get } misses generic parameter declaration. subscript<T>(index: Int) -> T { get } has mismatched types.

3. Final Answer:

   subscript<T>(index: T) -> String { get } -> Option D

4. Quick Check:

   Generic subscript syntax = subscript<T> [OK]

Hint: Generic subscript uses subscript<T>(index: T) syntax [OK]

Common Mistakes:

• Using func instead of subscript
• Omitting generic parameter <T>
• Mismatching parameter and return types

3. What will be the output of this Swift code?

struct Box {
    private var values = [String: Any]()
    subscript<T>(key: String) -> T? {
        get { values[key] as? T }
        set { values[key] = newValue }
    }
}

var box = Box()
box["age"] = 30
box["name"] = "Alice"
print(box["age"] as Int?, box["name"] as String?)

medium

A. Optional(30) Optional("Alice")

B. 30 Alice

C. nil nil

D. Compilation error

Solution

1. Step 1: Understand subscript behavior

   The subscript stores values in a dictionary with String keys and Any values, casting on get.

2. Step 2: Analyze stored values and prints

   "age" stores 30 (Int), "name" stores "Alice" (String). The print casts them back to Int? and String?, so output shows optionals.

3. Final Answer:

   Optional(30) Optional("Alice") -> Option A

4. Quick Check:

   Generic subscript returns optional cast values [OK]

Hint: Generic subscript returns optional cast values [OK]

Common Mistakes:

• Expecting non-optional output
• Confusing dictionary storage with direct types
• Assuming compilation error due to Any type

4. Identify the error in this generic subscript code and choose the fix:

struct Container {
    private var data = [Int: String]()
    subscript<T>(key: T) -> String? {
        get { data[key] }
        set { data[key] = newValue }
    }
}

medium

A. Change dictionary to [T: String] to match generic key type.

B. Add type constraint to subscript declaration.

C. Change subscript to subscript(key: Int) -> String? to match dictionary key type.

D. No error; code works as is.

Solution

1. Step 1: Check dictionary key type vs subscript key type

   Dictionary keys are Int, but subscript uses generic T which can be any type.

2. Step 2: Identify mismatch causing error

   Accessing data[key] fails because key is T, not necessarily Int. Fix is to restrict subscript key to Int.

3. Final Answer:

   Change subscript to subscript(key: Int) -> String? to match dictionary key type. -> Option C

4. Quick Check:

   Subscript key type must match dictionary key type [OK]

Hint: Subscript key type must match dictionary key type [OK]

Common Mistakes:

• Assuming generic T works without constraints
• Trying to change dictionary type without reason
• Ignoring type mismatch errors

5. Given a struct that stores values with keys of any Hashable type, how can you implement a generic subscript to safely get and set values?
Choose the best approach.

hard

A. Use separate dictionaries for each key type and switch inside the subscript.

B. Use a dictionary with keys of type AnyHashable and cast keys inside the subscript.

C. Use a dictionary with keys of type String only and convert all keys to String.

D. Use a generic dictionary [T: Any] without constraints and force cast keys.

Solution

1. Step 1: Understand requirement for any Hashable key

   To store values with keys of any Hashable type, use a dictionary with keys of type AnyHashable.

2. Step 2: Implement generic subscript with safe casting

   Use generic subscript with key of type T: Hashable, convert key to AnyHashable for dictionary access, ensuring type safety.

3. Final Answer:

   Use a dictionary with keys of type AnyHashable and cast keys inside the subscript. -> Option B

4. Quick Check:

   AnyHashable dictionary + generic subscript = safe flexible keys [OK]

Hint: Use AnyHashable keys for flexible generic subscripts [OK]

Common Mistakes:

• Using multiple dictionaries instead of one
• Converting all keys to String losing type info
• Force casting keys causing runtime errors