Algorithm and Data Structure
Welcome to the Algorithm and Data Structure series, where you can find a wealth of resources and solutions related to computer programming, algorithms, and data structures.
In today’s fast-paced technology-driven world, it’s more important than ever for software developers to have a strong understanding of the fundamental principles of algorithms and data structures. These concepts are the backbone of efficient and scalable computer programs, and they enable developers to solve complex problems and build innovative applications.
In this series, I provide a wide range of resources for programmers of all skill levels, from beginners to advanced professionals. This series includes step-by-step guides, and real-world examples, all designed to help you learn and master the essential concepts of algorithms and data structures.
Whether you’re looking to build your skills as a software developer, prepare for a technical interview, or simply learn more about the fascinating world of algorithms and data structures, this series has something for you. I invite you to explore, and share your feedback and suggestions.
Arrays
In computer programming, an array is a data structure that stores a fixed-size sequential collection of elements of the same data type. Each element in an array is assigned a unique index number that represents its position in the sequence.
Arrays are used in programming to store and manipulate collections of data. They are commonly used to store lists of values, such as numbers or strings, and provide a convenient way to access and modify individual elements in the list.
Arrays can be used in a wide variety of programming scenarios, including:
- Data storage and manipulation: Arrays can be used to store and manipulate large sets of data, such as lists of customer names, product prices, or inventory levels.
- Sorting and searching: Algorithms that sort or search through data often use arrays as a way to store and manipulate the data efficiently.
- Graphics and image processing: Arrays can be used to store and manipulate image and graphic data, such as pixels and color values.
- Mathematical operations: Arrays can be used to perform mathematical operations, such as vector or matrix operations in linear algebra.
- User interface design: Arrays can be used to store and manipulate user interface elements, such as buttons or menus.
In many programming languages, arrays are a fundamental data type that is supported by the language itself. They are used extensively in many programming languages, such as C, C++, Java, Python, and JavaScript, among others. Understanding how to use arrays effectively is an essential skill for any programmer who wants to build efficient and scalable programs.
1. Two Sum
Two Sum is a popular algorithm problem in computer science. The problem statement is as follows:
Given an array of integers nums and an integer target, you need to find two numbers in the array such that their sum is equal to the target. You are required to return the indices of these two numbers in the array.
To solve this problem, you can use a hash table to keep track of the previously visited numbers in the array. While iterating through the array, for each number num, you can check if the difference target - num is already in the hash table. If it is, then you have found the two numbers that add up to the target, and you can return their indices. Otherwise, you can add the current number and its index to the hash table and continue iterating.
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dict = [Int: Int]()
for (index, num) in nums.enumerated() {
let complement = target - num
if let complementIndex = dict[complement] {
return [complementIndex, index]
}
dict[num] = index
}
fatalError("No valid solution")
}
}The time complexity of this algorithm is O(n), where n is the length of the array nums, since we visit each number in the array only once.
2. Median of Two Sorted Arrays
The problem of finding the median of two sorted arrays can be solved using a divide-and-conquer approach. The key idea is to split the two arrays into two halves such that the number of elements in the left half of both arrays is equal to the number of elements in the right half of both arrays. Then, we can calculate the median by taking the average of the maximum value in the left half and the minimum value in the right half.
Here’s the Swift code that I implemented this algorithm:
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
let n1 = nums1.count
let n2 = nums2.count
// Ensure that nums1 has the smaller length
if n1 > n2 {
return findMedianSortedArrays(nums2, nums1)
}
var low = 0
var high = n1
while low <= high {
let partition1 = (low + high) / 2
let partition2 = (n1 + n2 + 1) / 2 - partition1
let maxLeft1 = partition1 == 0 ? Int.min : nums1[partition1 - 1]
let minRight1 = partition1 == n1 ? Int.max : nums1[partition1]
let maxLeft2 = partition2 == 0 ? Int.min : nums2[partition2 - 1]
let minRight2 = partition2 == n2 ? Int.max : nums2[partition2]
if maxLeft1 <= minRight2 && maxLeft2 <= minRight1 {
if (n1 + n2) % 2 == 0 {
return Double(max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0
} else {
return Double(max(maxLeft1, maxLeft2))
}
} else if maxLeft1 > minRight2 {
high = partition1 - 1
} else {
low = partition1 + 1
}
}
return 0.0
}This implementation uses binary search to find the median of the two sorted arrays. It makes sure that nums1 has the smaller length to reduce the number of partitions.
It then uses partition1 and partition2 to divide the two arrays such that maxLeft1 and maxLeft2 are the maximum values on the left side of the partition and minRight1 and minRight2 are the minimum values on the right side of the partition.
If the condition maxLeft1 <= minRight2 && maxLeft2 <= minRight1 is met, it means that we have found the median of the merged sorted array.
If the combined length of nums1 and nums2 is even, we take the average of the maximum value on the left and minimum value on the right. Otherwise, we just return the maximum value on the left. If maxLeft1 > minRight2, we search in the left half of nums1, otherwise we search in the right half of nums1.
The time complexity of this algorithm is O(log(min(m, n)))
Note: Here’s another approach of the same algorithm to find the median of two sorted arrays. The code works in a similar way as the previous implementation, but the implementation differs slightly.
class Solution {
func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
let m = nums1.count
let n = nums2.count
// If the first array is longer than the second, swap them
if m > n {
return findMedianSortedArrays(nums2, nums1)
}
var iMin = 0
var iMax = m
let halfLen = (m + n + 1) / 2
while iMin <= iMax {
let i = (iMin + iMax) / 2
let j = halfLen - i
if i < iMax && nums2[j-1] > nums1[i] {
iMin = i + 1
} else if i > iMin && nums1[i-1] > nums2[j] {
iMax = i - 1
} else {
var maxLeft = 0
if i == 0 {
maxLeft = nums2[j-1]
} else if j == 0 {
maxLeft = nums1[i-1]
} else {
maxLeft = max(nums1[i-1], nums2[j-1])
}
if (m + n) % 2 == 1 {
return Double(maxLeft)
}
var minRight = 0
if i == m {
minRight = nums2[j]
} else if j == n {
minRight = nums1[i]
} else {
minRight = min(nums1[i], nums2[j])
}
return Double(maxLeft + minRight) / 2.0
}
}
return 0.0
}
}Here’s a brief overview of the above implementation:
- I first check if the length of the first array is greater than the length of the second array. If it is, I swap the two arrays so that the first array is always the smaller one.
- Initialize the lower and upper bounds of the binary search to be 0 and the length of the first array, respectively.
- Loop through the array indices using binary search to find the partition indices for both arrays. I calculate the maximum value of the left half and the minimum value of the right half for both arrays.
- Check if the left half of the first array is less than or equal to the right half of the second array, and the left half of the second array is less than or equal to the right half of the first array. If this condition is true, I have found the median.
- If the maximum value of the left half of the first array is less than the minimum value of the right half of the second array, I move the partition index of the first array to the right. Otherwise, I move the partition index of the first array to the left.
- Return the median value.
The time complexity of this algorithm is also O(log(min(m, n)))
3. Container With Most Water
The Container With Most Water algorithm is a problem that asks to find the maximum area of water that can be contained in a container formed by a pair of vertical lines and the x-axis, given an array of non-negative integers representing the heights of the lines.
The algorithm works by using two pointers, one starting at the beginning of the array and the other starting at the end of the array. At each step, the algorithm calculates the area of the container formed by the two lines at the positions of the two pointers, and updates the maximum area seen so far if the calculated area is greater than the previous maximum. The width of the container is determined by the difference between the positions of the two pointers, and the height of the container is determined by the smaller of the two heights of the lines.
The reason for moving the pointer that points to the shorter line is that, if we move the pointer that points to the taller line, the height of the container will not increase, and the width of the container will decrease, which can only reduce the area of the container. On the other hand, if we move the pointer that points to the shorter line, the height of the container may or may not increase, but the width of the container will remain the same or decrease, which can only reduce the area of the container or leave it unchanged.
Here is my implementation of the solution in Swift:
func maxArea(_ height: [Int]) -> Int {
var left = 0, right = height.count-1
var maxArea = 0
while left < right {
let area = min(height[left], height[right]) * (right - left)
maxArea = max(maxArea, area)
if height[left] < height[right] {
left += 1
} else {
right -= 1
}
}
return maxArea}As I said I use two pointers, one starting at the beginning of the array (left) and the other starting at the end (right). At each iteration of the loop, I calculate the area of the container formed by the two lines at left and right, and update the maximum area seen so far if necessary. Then I move the pointer that points to the shorter line, since moving the other pointer would only reduce the width of the container and not increase its height.
The time complexity of this algorithm is O(n), where n is the length of the input array.
4. 3 Sum
The problem asks to find all unique triplets in an array of integers that add up to a given target sum. More formally, given an array of n integers nums and a target sum target, the goal is to find all unique triplets (a, b, c) such that a + b + c = target.
For example, given the input array nums = [-1, 0, 1, 2, -1, -4] and the target sum target = 0, the solution to the 3 sum problem is the set of unique triplets:
[-1, 0, 1]
[-1, -1, 2]The solution to the 3 sum problem can be obtained using various algorithms, such as brute force, two pointers, or hash map. The time complexity of the brute force algorithm is O(n³), since it involves iterating over all possible triplets of integers in the input array.
The time complexity of the two pointers algorithm is O(n²), since it involves sorting the input array and then iterating over all possible pairs of integers and using a third pointer to find the third integer that completes the triplet.
The time complexity of the hash map algorithm is O(n²), since it involves using a hash map to store the indices of the integers in the input array, and then iterating over all possible pairs of integers and using the hash map to find the third integer that completes the triplet.
Here’s my implementation of the solution in Swift using the two pointers algorithm:
func threeSum(_ nums: [Int]) -> [[Int]] {
var result: [[Int]] = []
let sortedNums = nums.sorted()
for i in 0..<sortedNums.count-2 {
if i > 0 && sortedNums[i] == sortedNums[i-1] {
continue // Skip duplicate values of i
}
var left = i+1, right = sortedNums.count-1
while left < right {
let sum = sortedNums[i] + sortedNums[left] + sortedNums[right]
if sum == 0 {
result.append([sortedNums[i], sortedNums[left], sortedNums[right]])
while left < right && sortedNums[left] == sortedNums[left+1] {
left += 1 // Skip duplicate values of left
}
while left < right && sortedNums[right] == sortedNums[right-1] {
right -= 1 // Skip duplicate values of right
}
left += 1
right -= 1
} else if sum < 0 {
left += 1
} else {
right -= 1
}
}
}
return result
}The idea of the two pointers algorithm is to fix one number (i) and then use two pointers to find two other numbers (j and k) that add up to the negative of the fixed number (i.e., j+k = -i).
The algorithm starts by sorting the input array, which allows me to skip duplicate values of i, j, and k.
Then, I iterate over all possible values of i, and for each value of i, I use two pointers (left and right) to find all pairs (j, k) that add up to -i. If the sum of the three numbers is equal to 0, I add the triplet to the result list and skip any duplicate values of left and right.
If the sum of the three numbers is less than 0, I increment left, since the sum must be increased. If the sum of the three numbers is greater than 0, I decrement right, since the sum must be decreased.
The time complexity of this algorithm is O(n²), where n is the length of the input array.
5. 3Sum Closest
It is variation of the 3Sum problem, where instead of finding all triplets that sum to a given target, the goal is to find the triplet that has the sum closest to a given target.
The goal of the 3Sum Closest problem is to find three integers in the array whose sum is closest to the target integer. The solution should return the sum of the three integers.
For example, given the input array nums = [-1, 2, 1, -4] and the target integer target = 1, the solution to the 3Sum Closest problem is the sum 2 (-1 + 2 + 1), since this is the closest sum to the target 1.
The solution to the 3Sum Closest problem can be obtained using a similar algorithm to the two pointers algorithm used for the 3Sum problem.
Here’s my implementation of the solution in Swift using the two pointers algorithm:
func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
let sortedNums = nums.sorted()
var closestSum = sortedNums[0] + sortedNums[1] + sortedNums[2]
for i in 0..<sortedNums.count-2 {
var left = i+1, right = sortedNums.count-1
while left < right {
let sum = sortedNums[i] + sortedNums[left] + sortedNums[right]
if abs(sum-target) < abs(closestSum-target) {
closestSum = sum
}
if sum == target {
return sum
} else if sum < target {
left += 1
} else {
right -= 1
}
}
}
return closestSum
}The algorithm starts by sorting the input array, which allows me to use the two pointers algorithm.
Then, I iterate over all possible values of the first number (i), and for each value of i, I use two pointers (left and right) to find the other two numbers (j and k) that add up to the target minus the fixed number (i.e., j+k = target — i).
At each iteration, I update the closest sum if the current sum is closer to the target than the current closest sum. If the current sum is equal to the target, I return it immediately.
If the current sum is less than the target, I increment the left pointer to increase the sum. If the current sum is greater than the target, I decrement the right pointer to decrease the sum.
The time complexity of this algorithm is O(n²), where n is the length of the input array, since I iterating over all possible values of i and using the two pointers algorithm to find the other two numbers.
6. 4Sum
4Sum is a variation of the 3Sum problem, where instead of finding all triplets that sum to a given target, the goal is to find all quadruplets (4-tuples) that sum to a given target.
Formally, given an array of n integers nums and a target integer target, the goal of the 4Sum problem is to find all 4-tuples (i, j, k, l) such that i < j < k < l and nums[i] + nums[j] + nums[k] + nums[l] = target.
For example, given the input array nums = [1, 0, -1, 0, -2, 2] and the target integer target = 0, the solution to the 4Sum problem is the set {(-2, -1, 1, 2), (-2, 0, 0, 2), (-1, 0, 0, 1)}, since these are the only 4-tuples that add up to the target 0.
To solve this problem, I can use a similar approach to the 3Sum and 4Sum problems, by fixing two elements and using two pointers to search for the other two elements. I need to be careful to avoid duplicates, since I am looking for unique quadruplets.
Here is the step-by-step approach:
- Sort the input array nums in non-decreasing order.
- Initialize an empty result array res.
- Iterate over the array nums, fixing the first element num1.
- For each num1, iterate over the remaining elements nums[i+1:] and fix the second element num2.
- Use two pointers to search for the third and fourth elements (num3 and num4), such that num1 + num2 + num3 + num4 = target.
- If such quadruplet (num1, num2, num3, num4) is found, add it to the result array res. Make sure to avoid duplicates by checking that num1, num2, num3, and num4 are distinct.
- Continue iterating over nums and return the result array res.
Here’s the Swift code for the fourSum function that solves the problem:
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
let nums = nums.sorted()
var result = [[Int]]()
for i in 0..<nums.count {
if i > 0 && nums[i] == nums[i-1] {
continue
}
for j in (i+1)..<nums.count {
if j > i+1 && nums[j] == nums[j-1] {
continue
}
var left = j+1
var right = nums.count-1
while left < right {
let sum = nums[i] + nums[j] + nums[left] + nums[right]
if sum == target {
result.append([nums[i], nums[j], nums[left], nums[right]])
while left < right && nums[left] == nums[left+1] {
left += 1
}
while left < right && nums[right] == nums[right-1] {
right -= 1
}
left += 1
right -= 1
} else if sum < target {
left += 1
} else {
right -= 1
}
}
}
}
return result
}The time complexity of this algorithm is O(n³), where n is the length of the input array nums. The space complexity is O(1), since I am using only a constant amount of extra space to store the result array.
7. Remove Duplicates from Sorted Array
The task is to remove the duplicates from a sorted array and return the new length of the array without duplicates.
Here’s the Swift code for the removeDuplicates function that solves the problem:
func removeDuplicates(_ nums: inout [Int]) -> Int {
if nums.isEmpty {
return 0
}
var j = 0
for i in 1..<nums.count {
if nums[i] != nums[j] {
j += 1
nums[j] = nums[i]
}
}
return j+1
}This function takes an integer array nums as input, which is assumed to be sorted, and returns an integer representing the new length of the array without duplicates.
The function uses two pointers, i and j, where i iterates over the array and j points to the last non-duplicate element.
The function compares the element at index i with the element at index j. If they are not equal, the function increments j, copies the element at index i to the new index j, and repeats the process for the next element.
Then returns j+1 as the new length of the array without duplicates.
