Dictionary creation and access in Swift - Time & Space Complexity

Time Complexity: Dictionary creation and access

O(1)

Understanding Time Complexity

When we create and access dictionaries, it is important to know how the time to do these actions changes as the dictionary grows.

We want to understand how fast or slow these operations become when the dictionary has more items.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

var ages: [String: Int] = [:]

// Adding items
ages["Alice"] = 30
ages["Bob"] = 25
ages["Charlie"] = 35

// Accessing an item
let aliceAge = ages["Alice"]

This code creates a dictionary, adds three entries, and then accesses one entry by its key.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or accessing a single key-value pair in the dictionary.
• How many times: Each add or access happens once per key; no loops or repeated traversals here.

How Execution Grows With Input

Adding or looking up a key in a dictionary takes about the same time no matter how many items are inside.

Input Size (n)	Approx. Operations
10	About 1 operation per add or access
100	Still about 1 operation per add or access
1000	Still about 1 operation per add or access

Pattern observation: The time to add or access does not grow much as the dictionary gets bigger.

Final Time Complexity

Time Complexity: O(1)

This means adding or accessing a value in a dictionary takes about the same short time no matter how many items are stored.

Common Mistake

[X] Wrong: "Accessing a dictionary item takes longer as the dictionary gets bigger because it searches through all items."

[OK] Correct: Dictionaries use a special method to jump directly to the item, so they don't check every entry one by one.

Interview Connect

Understanding dictionary time complexity helps you explain why certain data structures are fast and efficient, a useful skill in many coding discussions.

Self-Check

"What if we tried to find a value by searching through all keys instead of using the dictionary's direct access? How would the time complexity change?"

Practice

1. What is a dictionary in Swift used for?

easy

A. To store data in key-value pairs for quick lookup

B. To store a list of values without keys

C. To perform mathematical calculations

D. To create user interface elements

Solution

1. Step 1: Understand dictionary purpose

   Dictionaries store data as pairs of keys and values, allowing fast access by key.

2. Step 2: Compare options

   Only To store data in key-value pairs for quick lookup correctly describes this key-value storage purpose.

3. Final Answer:

   To store data in key-value pairs for quick lookup -> Option A

4. Quick Check:

   Dictionaries = key-value storage [OK]

Hint: Remember: dictionaries pair keys with values for fast access [OK]

Common Mistakes:

• Confusing dictionaries with arrays (which have no keys)
• Thinking dictionaries perform calculations
• Assuming dictionaries create UI elements

2. Which of the following is the correct way to create a dictionary in Swift?

easy

A. let dict = ("apple", 1), ("banana", 2)

B. let dict = ["apple": 1, "banana": 2]

C. let dict = {"apple": 1, "banana": 2}

D. let dict = ["apple", 1, "banana", 2]

Solution

1. Step 1: Identify Swift dictionary syntax

   Swift dictionaries use square brackets with key-value pairs separated by colons.

2. Step 2: Check each option

   let dict = ["apple": 1, "banana": 2] uses correct syntax: ["key": value, ...]. Others use tuples, braces, or arrays incorrectly.

3. Final Answer:

   let dict = ["apple": 1, "banana": 2] -> Option B

4. Quick Check:

   Dictionary syntax = [key: value] [OK]

Hint: Use square brackets with colons for key-value pairs [OK]

Common Mistakes:

• Using parentheses instead of square brackets
• Using curly braces which define closures
• Listing keys and values without colons

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

let fruits = ["apple": 3, "banana": 5]
print(fruits["banana"] ?? 0)

medium

A. 5

B. nil

C. banana

D. 0

Solution

1. Step 1: Access dictionary value by key

   fruits["banana"] looks up the value for key "banana", which is 5.

2. Step 2: Use nil-coalescing operator

   The ?? 0 means if the key is missing (nil), print 0; here key exists, so print 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fruits["banana"] = 5 [OK]

Hint: Use ?? to provide default if key missing [OK]

Common Mistakes:

• Expecting nil instead of default value
• Printing the key instead of the value
• Confusing optional with direct value

4. Identify the error in this Swift code snippet:

var scores = ["Alice": 90, "Bob": 85]
scores["Charlie"] = 95
print(scores["Charlie"])

medium

A. Cannot add new key-value pairs to a dictionary

B. Dictionary keys must be integers

C. Syntax error in dictionary declaration

D. Missing unwrap of optional when printing

Solution

1. Step 1: Check dictionary modification

   Adding a new key-value pair to a var dictionary is allowed, so no error there.

2. Step 2: Understand optional access

   Accessing scores["Charlie"] returns an optional Int?; printing it directly shows Optional(95), not 95.

3. Step 3: Identify missing unwrap

   To print the value without Optional(...), unwrap it safely or use ?? to provide default.

4. Final Answer:

   Missing unwrap of optional when printing -> Option D

5. Quick Check:

   Dictionary access returns optional, unwrap needed [OK]

Hint: Remember dictionary access returns optional, unwrap before use [OK]

Common Mistakes:

• Thinking keys must be integers
• Assuming dictionary is immutable by default
• Ignoring optional nature of dictionary values

5. Given a dictionary let items = ["pen": 3, "notebook": 0, "eraser": 2], which Swift code correctly creates a new dictionary containing only items with quantity greater than zero?

hard

A. let filtered = items.compactMap { $0.value > 0 }

B. let filtered = items.filter { $0.key > 0 }

C. let filtered = items.filter { $0.value > 0 }

D. let filtered = items.map { $0.value > 0 }

Solution

1. Step 1: Understand filtering dictionary by value

   We want to keep pairs where value > 0, so filter with condition on $0.value.

2. Step 2: Analyze each option

   let filtered = items.filter { $0.value > 0 } uses filter with correct condition. let filtered = items.filter { $0.key > 0 } incorrectly compares key (a String) to 0. Options A and C use map/compactMap which transform values, not filter pairs.

3. Final Answer:

   let filtered = items.filter { $0.value > 0 } -> Option C

4. Quick Check:

   Filter dictionary by value > 0 = let filtered = items.filter { $0.value > 0 } [OK]

Hint: Use filter with $0.value condition to keep matching pairs [OK]

Common Mistakes:

• Filtering by key instead of value
• Using map instead of filter for selection
• Using compactMap which changes type, not filters