Day 11 of 30 days of Data Structures and Algorithms and System Design Simplified — Arrays
Welcome back peeps. Hope all’s well. In this post we will cover Arrays as follows —
What and Why Arrays(in 2–3 sentences)?
How does Arrays work?
Important Patterns and Techniques in Arrays Questions
Most Important Questions with Solutions
Tips and Techniques to solve Arrays Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Arrays
Importance : High
Note : New Arrays questions with solutions are added every day . So keep checking this post daily.
Let’s dive in!
What is Arrays ?
Array is a collection of elements stored in a contiguous fashion/memory locations where the index of the first element start at 0. The length of an array is the total number of elements in it.
In python, the array is nothing but a list where you can store elements of different data types and the indexing starts from 0 for the first element and to access the last element ( in reverse fashion) you can use the location as -1.
Examples of Arrays problems —
Find Subarrays With Equal Sum
Palindromes
Search in sorted/unsorted array
Two Sum
Subsequence
Rotate an array
Merge two arrays/lists
How does Array work?
Arrays work by allocating a block of memory to hold the elements, and each element is assigned a unique index (also called a subscript) that can be used to directly access and manipulate the element. The elements are stored in contiguous memory locations, which allows for fast and efficient access using the index.
Arrays are collections of objects which can be of same/different data types. It allocates the elements to contiguous memory indexes/locations so that one can insert, delete, update and append the array.
Arrays in python are known as lists and it has various methods to perform different operations ( as shown in the pic below)
One can also perform in-place operations in the array which means modifying the array without creating a new Array. This can be done by shifting the existing elements.
Important Patterns and Techniques in Arrays Questions
Array questions involve one or more of arrays operations using the array methods listed above. Know how to implement these methods to make an easy sail when asked an array/list question.
Important patterns and techniques in arrays questions include:
- Two Pointers: This technique is used to traverse the array and find a specific element or pattern. It is commonly used in problems involving sorting, searching, and removing duplicates.
- Sliding Window: This is a technique used to keep track of a “window” of elements in an array, and is often used to find the maximum or minimum value in a subarray.
- Dynamic Programming: This technique is used to solve problems by breaking them down into smaller subproblems, and is often used to find the maximum or minimum value in an array.
- Hash Table: This data structure is used to efficiently store and retrieve elements in an array, and is often used to find duplicates or check for the presence of an element in an array.
- Sort: Sorting is a fundamental operation that is often used to order elements in an array, and it can be used to solve many different types of problems.
Patterns → Questions like below belong to Arrays ( not limited to):
Find Subarrays With Equal Sum
Jump Game
Gas Stations
Palindromes
Search in sorted/unsorted array
Two Sum
Subsequence
Rotate an array
Merge two arrays/lists etc
Most Important Questions with Solutions
Note : New Arrays questions with solutions are added every day . So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important Arrays questions.
Two Sum
Question —
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example :
Input: nums = [2,7,11,15], target = 9
Output: [0,1]Solution :
Main Logic/Idea —
The main logic is to use a hashmap for {value : index }. Then calculate the target sum by taking the difference between target and the num[i] and then store in the hashmap to check if the difference is already there in the hashmap or not. If found, then return the index of the num and index at which difference is located in the hashmap.
Implementation —
def twoSum(self, nums: List[int], target: int) -> List[int]:
res = {}
for index, num in enumerate(nums):
ans = target - num
if ans in res:
return [res[ans],index]
res[num] = index
returnQuestion Link
Similar Pattern —
Number of Pairs of Strings With Concatenation Equal to Target
Find All K-Distant Indices in an Array
Check Distances Between Same Letters
Two Sum III — Data structure design
Count Number of Pairs With Absolute Difference K
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Search in Rotated Sorted Array
Question —
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
Example :
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4Solution :
Main Logic/Idea —
Since the array is sorted, the main logic is to take the mid and compare the left and right side of the array. If the comparison condition satisfies one of the criteria then increment left pointer/decrement right pointer accordingly till left pointer is less than equal to the right pointer.
Implementation —
def search(self, nums: List[int], target: int) -> int:
left, right = 0,len(nums) -1
while left <= right :
m = ( left + right)//2
if target == nums[m]:
return m
if nums[left] <= nums[m]:
if target > nums[m] or target < nums[left]:
left = m +1
else:
right = m-1
else:
if target < nums[m] or target > nums[right]:
right = m -1
else:
left = m +1
return -1Question Link
Similar Pattern —
Search in Rotated Sorted Array II
Pour Water Between Buckets to Make Water Levels Equal
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Merge Sorted Array
Question —
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example :
Input : nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]Solution :
Main Logic/Idea —
Since both the array are sorted, take the length of both the arrays in a variable and then start comparing the values if nums1 and nums2 at index m and n. If the comparison condition satisfies one of the criteria then decrement m or n pointer accordingly and store the value at index l.
Implementation —
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
l = m+n-1
while m>0 and n>0:
if nums1[m-1] > nums2[n-1]:
nums1[l] = nums1[m-1]
m -=1
else:
nums1[l] = nums2[n-1]
n -=1
l-=1
while n>0:
nums1[l] = nums2[n-1]
n,l = n-1, l-1Question Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Arrays questions with solutions will be added every day. So keep checking this post daily.
Complexity Analysis
Read complexity analysis post before reading the complexities for Array operations.
To create the array —
Time Complexity: O(1)
Space: O(n)
For insertion and deletion at the beginning
O(n) if array is not full
Insertion at the end of array
O(1)
Deletion at the end of array
O(1)
Insertion in the middle
O(n)
Deletion in the middle
O(n)
Indexing the array
O(1)
Search an item in the array
O(n)
Tips and Techniques to solve Arrays Questions Fast
Array questions are some of the most easiest to hardest questions. Remember the fundamental rule — array stores the objects/elements in sequential manner i.e in contiguous memory locations.
To solve the array questions fast —
- Before thinking about any possible solution first see if the array is sorted or not. If’s its sorted then most likely the solution involves binary search.
- Know and implement the most important list methods ( as shown above in point 2)
- Know how to implement recursion.
- Know how to manipulate indexes and retrieve values
- Know how to reverse, sort and slice the arrays.
That’s it for now. Day 12: Strings coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
