Why
Arrays Still Run the Tech World (Before We Touch Any Question)
You daily use systems that utilize arrays to function. Arrays
allow for the machines you use every day to operate. This is not through flashy
or sophisticated algorithms, nor through AI buzzwords, but rather through
structured and indexed data that allows for rapid use. Each time you examine
stock prices for a specific period of time, you are examining arrays. Each time
you review usage logs of users, you are examining arrays. Each time you review
the most relevant search results, you are reviewing arrays. Each time you work
with sensor data, clickstream data, and time-series metrics, you are utilizing
arrays.
The question asked by modern computing equipment has changed
from "Can I create a data storage structure?" to "Can I process
large amounts of information on a continual basis?" because of how
effectively arrays can store and process large amounts of data. Arrays allow
for:
• Predictable memory layout
• Constant time index access
• Cache friendly performance
• Simple layouts that scale exponentially
When you have an array incorrectly defined, you will notice
performance degradation. However, when you fully understand how to define and
use arrays correctly, you will see that everything built above arrays becomes
easier.
Most interviews begin at arrays, and we will also begin with
arrays as we prepare you for interviews and working in the real world. We will
not be focusing on any theories or academic definitions. We will study how the
arrays market uses the array, through solving real-world problems that require
you to think efficiently. Let's start!
🟢 EASY SECTION: Getting Comfortable
with the Data
1️. Two Sum
🧠Explanation
An immediate
thought is to use a nested loop, but this method takes O(n²) time and so would
be likely to run into time limits (TLE) quite quickly with larger inputs. By
using a hash map, we avoid having to make unnecessary comparisons.
⚙️Logic in Steps
1. Create a
dictionary that will contain numbers and their corresponding indices.
2. Iterate
through the array a single time.
3. For each
number:
a. calculate
its complement to meet the target,
b. if its
complement is in the dictionary, return both indices,
c. if not,
add the current number to the dictionary with the current index.
2️. Contains Duplicate
🧠Explanation
The reason
we are able to remove duplicate elements from an already sorted array and save
the space in our memory by doing so is due to the fact that all duplicates will
be located next to each other because it is sorted.
⚙️Logic in Steps
The process
for removing duplicates from a sorted array consists of:
- First
check if the array has any elements. If not, then we will return 0.
- Create a
pointer (j) that represents where the next unique element will be placed.
- We will
start iterating through the array from index 1 (not from index 0).
- If the
current element is different from the previous element(s), we know it is a
unique value and we will place this unique value in position j of the array.
- We will
then move j forward to the next available position where we can put the next
unique number.
- After the
loop is complete, we will have a count of all of the unique numbers in the
first j positions of the array.
3️. Best Time to Buy and Sell Stock
🧠Explanation
The most
obvious solution for this issue is brute force, and we can do this by looping through every combination of the days we can buy and sell using nested loops.
However, this is inefficient as it has a time complexity of O(n²), especially
for large arrays. The optimal solution to this issue is using a single pass
method
⚙️Logic in Steps
1.
We
will set the first price into our min_price and the max_profit into 0.
2.
Then,
we will start from the second element and iterate through the rest of the
array:
3.
If
the current price is less than the min_price, then we will make the min_price
the current price.
4.
If
it is not, then we will calculate the profit (current price - min_price) and
set the max_profit if it is greater than the previous max_profit.
5.
Lastly,
return max_profit.
This is the
most efficient way to find the maximum profit and does not require checking
against each combination of buy/sell days. The time complexity and space complexity
for this solution is O(n) and O(1), respectively. Therefore, it is also the
best choice for large datasets.
4️. Pascal’s Triangle
🧠ExplanationThe
brute-force method (multiple nested loops) is usually the first method that
comes to mind for creating Pascal's Triangle by updating the triangle with
successive additions of each pair of adjacent entries from the previous row.
While this method works, it produces bulky, unreadable code because of the
nested loop structure used to input into the current triangle.
There is,
however, a much cleaner and more optimal method using the simple building upon
of the last element previously generated by appending each new row of the
triangle to the last row as you build up the triangle.
⚙️Logic in Steps
1.
Start
with the first row [1].
2.
For
every next row:
- Take the previous row.
- Compute inner elements by adding
consecutive elements from the previous row.
- Add 1 at the beginning and end
of the row.
3.
Append
each newly generated row to the triangle.
4.
Repeat
until numRows rows are generated.
🟡 MEDIUM SECTION: Patterns Start
Appearing
5️. Container With Most Water
🧠Explanation
The brute
force method, which is the most obvious solution, simply iterates through every
pair of lines using nested loops in order to retrieve the area formed by those
lines. Unfortunately, this is very inefficient with a time complexity of O(n²).
Therefore, it will take an extended period of time for large amounts of input.
By applying
the Two-pointer technique, we can locate the maximum area of a container with
only a single pass.
⚙️Logic in Steps
1.
Initialize
two pointers:
- left at the beginning of the
array
- right at the end of the array
2.
While
left < right:
- Calculate the width as right -
left.
- The height of the container is
the minimum of the two lines at left and right.
- Compute the area as width ×
height.
- Update max_area if the current
area is larger.
3.
Move
the pointer pointing to the shorter line inward, because the area is limited by
the shorter height and moving the taller line won’t increase the area.
4.
Continue
until both pointers meet.
5.
Return
max_area.
6️. 3Sum
Normally,
when faced with this problem, we would create a brute-force method for finding
all the possible triplet combinations. Utilizing three nested loops (O(n³) time
complexity), this would be an extremely inefficient way to check every possible
combination of triplets within a single input.
By implementing a solution that takes advantage of both sorting and employing
two-pointer techniques, we can reduce the overall time complexity of finding a
valid triplet by utilizing sorting and significantly reduce the computational
burden of checking for duplicate triplets.
⚙️Logic in Steps
- First, sort the array. Sorting
helps in using the two-pointer technique and makes it easier to avoid
duplicate triplets.
- Iterate through the array using
index i, fixing one element at a time.
- Skip duplicate elements for i to
ensure the result contains only unique triplets.
- For the remaining part of the
array, use two pointers:
- left starting from i + 1
- right starting from the end of
the array
- Set the target as -nums[i]. Now
we need to find two numbers whose sum equals this target.
- While left < right:
- If the sum of nums[left] and nums[right]
equals the target, store the triplet.
- Skip duplicate values for both left
and right pointers.
- Move both pointers inward.
- If the sum is smaller than the
target, move left forward.
- If the sum is greater than the
target, move right backward.
- Continue until all valid
triplets are found.
⏱️ Time Complexity: O(n²)
📦 Space Complexity: O(1)
(excluding the output list)
Once you
crack this, you unlock an entire family of problems.
7️. 3Sum Closest
🧠ExplanationThe most
straightforward method in solving this problem is to use a brute force method
by checking the sums of all permutations of triplets with three separate loops,
comparing each sum to the target. Unfortunately, this leads to O(n³) time
complexity for large arrays resulting in an inefficient algorithm.
The optimal solution is an improvement on the sorting, using the same method as
in 3Sum but rather than finding the exact total sum, we will look for a value
that is closest to the target value. To eliminate the two pointers method after
sorting, we can only solve the problem through a single pass that uses only two
pointers, instead of three distinct passes, which speeds up the algorithm
significantly.
⚙️Logic in Steps
- First, sort the array. Sorting
allows us to use the two-pointer approach efficiently.
- Initialize closest_sum using the
sum of the first three elements. This acts as our initial reference.
- Fix one element at index i and
use two pointers:
- left starting from i + 1
- right starting from the end of
the array
- Calculate the current sum of the
triplet.
- If the absolute difference
between current_sum and target is smaller than that of closest_sum,
update closest_sum.
- Move the pointers based on
comparison with the target:
- If current_sum is smaller than
the target, move left forward.
- If current_sum is greater than
the target, move right backward.
- If current_sum equals the
target, return it immediately since this is the closest possible value.
- Continue until all valid
combinations are checked.
- Return closest_sum.
⏱️ Time
Complexity: O(n²)
📦 Space
Complexity: O(1)
8️. Remove Duplicates from Sorted Array
🧠Explanation
You may
first consider using the brute-force approach to this problem of finding four
numbers whose sum is equal to a given number, by writing four nested loops that
iterate through all possible quadruples. This results in a time complexity of
O(n⁴), which is not practical when dealing with larger inputs.
Instead of using the brute force method, we can utilize an optimized version of
the 3-Sum algorithm by fixing two of the four numbers and applying a two
pointer method to find the other two numbers from the remaining elements of the
sorted array.
⚙️Logic in Steps
- First, sort the array. Sorting
helps in applying the two-pointer approach and handling duplicates
efficiently.
- Fix the first number using index
i.
- Skip duplicate values for i to
avoid repeated quadruplets.
- Fix the second number using
index j.
- Again, skip duplicate values
for j.
- For the remaining part of the
array, use two pointers:
- left starting from j + 1
- right starting from the end of
the array
- Calculate the sum of the four
elements:
- If the sum equals the target,
store the quadruplet.
- Skip duplicate values for left
and right.
- Move both pointers inward.
- If the sum is smaller than the
target, move left forward.
- If the sum is greater than the
target, move right backward.
- Continue until all valid
quadruplets are found.
⏱️ Time Complexity: O(n³)
📦 Space Complexity: O(1) (excluding the output
list)
This mirrors
real production constraints.
🧠If you have missed the previous blog
The previous
blog should help clarify the importance of Time and Space Complexity and how
the understanding of it will allow you to better design your code for real life
situations, versus creating code that works in an isolated environment.
Time and Space Complexity Explained: A Practical Guide with Python Examples
Coming Next
Next week we
will cover Stacks in Python, which may appear to be an uncomplicated data
structure, but it is the underlying technology of many everyday operations. The
stack is also used in many real interviews as a coding challenge. Once you have
completed studying Arrays and Pointers and you have a good feeling for what
they mean and how to use them, Stacks will show you how to fit the pieces of
the puzzle together to create an effective logic solution.
Mastering Stack Data Structures: Easy to Medium LeetCode Problems Explained
🔚
Closing Whispers
In every
loop refined and every pointer aligned,
Efficiency teaches discipline to the curious mind.
Code that scales is more than logic written right,
It’s thought made timeless, sharpened by insight.
If you liked this,
Follow Raw Unfiltered Talks
Comments
Post a Comment