Understanding time complexity is very important in algorithm problem solving. Time complexity is a key factor in evaluating the efficiency of an algorithm, indicating how quickly the algorithm runs based on the given input size. In this course, we will analyze time complexity while solving algorithm problems using Swift and learn how to write efficient code through this process.
Problem: Finding Common Elements in Two Arrays
You are given two integer arrays, A and B. Write a function that returns an array containing all the elements that are common to both arrays.
Problem Description
- Input: Two integer arrays
AandB(0 ≤ A.length, B.length ≤ 1000) - Output: An array containing the common elements from both arrays (duplicates excluded)
Example
Input: A = [1, 2, 3, 4, 5], B = [3, 4, 5, 6, 7]
Output: [3, 4, 5]
Solution Process
1. Understanding the Problem
This is a problem of finding the common elements from the given two arrays, excluding duplicates.
Since the size of each array can be up to 1000, we may need to compare a maximum of 2,000 elements.
Therefore, it can be solved with a simple nested loop that has O(n^2) complexity, but let’s explore a more efficient solution.
2. Exploring Efficient Methods
To find the common elements, let’s consider comparing the two arrays, listing their elements and thinking of ways to avoid duplicates.
Utilizing a HashSet can solve this with O(n) time complexity.
First, we’ll store the elements of array A in a HashSet, then traverse through array B to check for elements that exist in the HashSet.
3. Implementing Swift Code
func findCommonElements(A: [Int], B: [Int]) -> [Int] {
var setA = Set(A) // Store elements of array A in a HashSet
var result: [Int] = [] // Array to store the results
for element in B { // Traverse each element of array B
if setA.contains(element) { // Check if it exists in the HashSet
result.append(element) // If it exists, add to result array
setA.remove(element) // Remove from HashSet to avoid duplicates
}
}
return result
}
// Example execution
let A = [1, 2, 3, 4, 5]
let B = [3, 4, 5, 6, 7]
let commonElements = findCommonElements(A: A, B: B)
print(commonElements) // Output: [3, 4, 5]
4. Analyzing Time Complexity
In the above code, adding elements to the HashSet takes O(1) time, leading to O(n) time based on the size of array A.
Subsequently, traversing through array B to check each element in the HashSet also takes O(1) time.
Therefore, the overall time complexity is O(n + m), where n is the size of array A and m is the size of array B.
This is much more efficient compared to the original O(n^2) approach.
Conclusion
Analyzing time complexity during the process of solving algorithm problems is essential.
Always keep in mind that choosing an algorithm with optimal time complexity can greatly enhance the performance of your code.
Through solving this problem using Swift, I hope you have practiced writing efficient algorithms by leveraging time complexity.
Continue to build your skills by solving various algorithm problems!