10, Aug 2024
Array Manipulation Challenges
Okay, so sometimes the little things matter a whole lot, it may sound odd but I've found great benefit in taking a break from the big stuff and returning to the bare basics every once in a while. So let's play around a bit with one of these basics: Arrays.
Arrays are like the Swiss-army knife of programming; versatile and indispensable. But, just like that knife, they come with their own set of challenges. In this post, we’re going to explore some common array manipulation challenges and how to tackle them using Swift.
1. Reversing an Array
Let’s start with a classic: reversing an array. Sounds straightforward, right? But it’s a great way to get familiar with array manipulation.
Problem: Given an array of integers, reverse its elements.
Example:let arr = [1, 2, 3, 4, 5]
// Expected Output: [5, 4, 3, 2, 1]
Solution:In Swift, this is quite simple, all you need to use is
Array.reversed():
print(arr.reversed()) // Output: [5, 4, 3, 2, 1]
Here,
arr.reversed() returns a reversed collection of the array. Note that it returns a `ReversedCollection` rather than a new array, so you probably will need to convert it back to an array by using
Array(ReversedCollection).
An advanced solution would use two pointers to swap elements of the array in-place, can you work it out?
2. Finding the Maximum Product of Two Elements
Another easy one. We need to find the maximum product of any two elements in an array of integers.
Example:let arr = [1, 10, 2, 6, 5]
// Expected Output: 60 (because 10 • 6 = 60)
Solution:This becomes a trivial issue if only you sort the array first:
func maxProduct(_ arr: [Int]) -> Int? {
guard arr.count >= 2 else { return nil }
let sortedArr = arr.sorted()
return sortedArr[sortedArr.count - 1] • sortedArr[sortedArr.count - 2]
}
print(maxProduct(arr)) // Output: 60
Sorting will make the last two elements guaranteed to be the largest, so their product will be the maximum.
A better solution would avoid sorting and use a single pass to find the two largest numbers.
3. Finding the Missing Number
This challenge often pops up in coding interviews and is a good test of your problem-solving skills.
Problem: Given an array containing (n) distinct numbers taken from 0 to (n), find the one number that is missing.
Example:let arr = [0, 1, 3]
// Expected Output: 2
Solution:Here’s a nifty trick using the sum of numbers:
func findMissingNumber(_ arr: [Int]) -> Int {
let n = arr.count
let totalSum = (n • (n + 1)) / 2
let arraySum = arr.reduce(0, +)
return totalSum - arraySum
}
print(findMissingNumber([0, 1, 3])) // Output: 2
The formula
(n (n + 1)) / 2• computes the sum of the first (n) natural numbers. By subtracting the sum of the array from this value, you get the missing number.
Keep in mind that this solution is limited to only one number missing in a perfect sequence.
4. Rotating an Array
Rotating an array means shifting its elements around. It’s like turning the array to the left or right.
Problem: Rotate an array to the right by (k) steps.
Example:let arr = [1, 2, 3, 4, 5, 6, 7]
let k = 3
// Expected Output: [5, 6, 7, 1, 2, 3, 4]
Solution:The bruteforce way world be to loop for
k and bring the last element to the beginning of the array, but here's a smarter way:
func rotateArray(_ arr: [Int], by k: Int) -> [Int] {
let k = k % arr.count // In case k is greater than the length of the array
return Array(arr[(arr.count - k)...] + arr[..<(arr.count - k)])
}
print(rotateArray([1, 2, 3, 4, 5, 6, 7], by: 3)) // Output: [5, 6, 7, 1, 2, 3, 4]
By dividing (slicing) up the array into two parts and then concatenating them in reverse, you achieve the rotation. Imagine this happening with an array of 1,000,000 elements vs the bruteforce method to appreciate why this solution is much superior.
5. Finding the Intersection of Two Arrays
Finding common elements between two arrays is a problem with various applications. We will keep it simple by finding out only elements that appear in both arrays at the same time.
Problem: Given two arrays, find the intersection of the two.
Example:let arr1 = [1, 2, 2, 1]
let arr2 = [2, 2]
// Expected Output: [2, 2]
Solution:You can use a dictionary to count occurrences:
func intersectArrays(_ arr1: [Int], _ arr2: [Int]) -> [Int] {
var countDict = [Int: Int]()
var intersection = [Int]()
for num in arr1 {
countDict[num, default: 0] += 1
}
for num in arr2 {
if let count = countDict[num], count > 0 {
intersection.append(num)
countDict[num] = count - 1
}
}
return intersection
}
print(intersectArrays([1, 2, 2, 1], [2, 2])) // Output: [2, 2]
Using a dictionary helps track and count elements from both arrays. This method is clever in that in using a
count dictionary, it ensures that an element is only counted once from both sides.
An evolution of this problem is
Finding the biggest common sub-array which requires finding the biggest array that appears exactly in both original arrays with its same sequence.
6. Implementing a Moving Average
Moving averages are used in various applications, including financial data analysis and signal processing.
Problem: Compute the moving average of a given window size over an array.
Example:let arr = [1, 2, 3, 4, 5, 6, 7, 8]
let windowSize = 3
// Expected Output: [2.0, 3.0, 4.0, 5.0, 6.0, 7.0]
Solution:We can use a sliding window approach:
func movingAverage(_ arr: [Int], windowSize: Int) -> [Double] {
guard windowSize <= arr.count else { return [] }
var averages = [Double]()
var windowSum = arr.prefix(windowSize).reduce(0, +)
averages.append(Double(windowSum) / Double(windowSize))
for i in windowSize..<arr.count {
windowSum += arr[i] - arr[i - windowSize]
averages.append(Double(windowSum) / Double(windowSize))
}
return averages
}
print(movingAverage([1, 2, 3, 4, 5, 6, 7, 8], windowSize: 3)) // Output: [2.0, 3.0, 4.0, 5.0, 6.0, 7.0]
The cool thing about this solution, is that
windowSum is calculated once, then with every iteration, we only subtract the value of the first value from the previous window while adding the new value from the new windows (think of
windowSize being huge and it'll be obvious why this is an advantage).
I really hope you enjoyed playing around with arrays with these simple problems. Such examples, simple as they may seem, really open up the mind to greater solutions to bigger -real world- challenges.
If you’re trying your own solutions, remember to keep your code clean and efficient. Experiment with different approaches, and don’t hesitate to try out different languages or techniques. Happy coding, and may your arrays always be well-managed!
