All programmers out there in the quest of conquering the world of programming are well aware of the modalities of data structures and algorithms. Indeed, DSA is the most important fundamental for building concepts and acumen to solve real-world programming problems.
As there exists a variety of data structures and algorithms in terms of complexity, difficulty, application, and usage, programmers often face an impasse where they become perplexed by not being able to figure out their initial go-to data structure.
Don’t worry, we got you covered as always! Undoubtedly, arrays are the most fundamental data structure and fairly simple to comprehend for a beginner in the programming world. Arrays are widely used as a pre-requisite or basis in multiple data structures, which gives them immense importance and application.
In a nutshell, an array is a sequential collection of elements of the same data type which stores data elements in form of continuous memory. The elements of an array are accessed by using an index where it could range from 0 to N−1, N being the size of the array.
In this blog, we bring out some exhaustive yet basic problems with a basic road map in the context of arrays that will itch your brain cells to activate the grey matter and test your true competence in the world of arrays.
Video Tutorial- https://bit.ly/3teelfS
Fasten your seatbelts and hustle to greet ARRAYS -
- Next Permutation -
Given a sequence of integers in an array, find the “next permutation” of the sequence.
If the current permutation is the final permutation in the permutation sequence, return an array sorted in ascending order.
Here is an example permutation sequence:
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
Here is how that was constructed:
,,_ (can use: 1,2,3)
1,_,_ (can use: 2,3)
1,2,_ (can use: 3)
1,2,3 Permutation #1 (choices exhausted — backtrack)
1,2,_ (can use: 3) (already placed 3 — backtrack)
1,_,_ (can use: 3, 2)
1,3,_ (can use: 2)
1,3,2 Permutation #2 (choices exhausted — backtrack)
1,3,_ (can use: 2) (already placed 2 — backtrack)
1,_,_ (can use: 2, 3) (already placed 3 — backtrack)
,,_ (can use: 2, 3, 1)
2,_,_ (can use: 3, 1)
2,1,_ (can use: 3)
2,1,3 Permutation #3 (choices exhausted — backtrack)
… and so on
Example 1:
Input: [1,2,3]
Output: [1,3,2]
Example 2:
Input: [1,5,2]
Output: [2,1,5]
Example 3:
Input: [3,2,1]
Output: [1,2,3] # Cycle back around to the first permutation
Follow-up:
Can you solve this in O(n) time?
Can you solve this only using O(1) space?
Constraints:
The sequence is conceptually created by placing the least (lowest in value) unplaced item for that slot when it comes time to choose a placement
0 <= n <= 100 (where n is the length of the array)
- Rotating a 2D Matrix -
Given a two-dimensional square matrix (n x n), rotate the matrix 90 degrees to the right (clockwise).
Example 1:
Input:
[
[ 1, 2, 3, 4],
[ 5, 6, 7, 8],
[ 9, 10, 11, 12],
[13, 14, 15, 16]
],
Output:
[
[13, 9, 5, 1],
[14, 10, 6, 2],
[15, 11, 7, 3],
[16, 12, 8, 4]
]
Example 2:
Input:
[
[10, 20],
[30, 40]
],
Output:
[
[30, 10],
[40, 20]
]
Challenge:
- Can you do the rotation in place?
- The 3-Sum Problem -
Given an array of n integers, return all unique triplets [a,b,c] in the array such that a + b + c = 0.
Example 1:
Input:
[-3, -1, 1, 0, 2, 10, -2, 8]
Output:
[
[-3, 1, 2],
[-2, 0, 2],
[-1, 0, 1]
]
Example 2:
Input:
[-5, 3, 2, 0, 1, -1, -5, 3, 2]
Output:
[
[-5, 2, 3], # the same triplet is not duplicated
[-1, 0, 1]
]
Example 3:
Input:
[1, 2, 3, 4]
Output:
[] # no triplets found that sum to zero
Note
- Duplicate triplets are not allowed in the output
- Enumerate All Primes To N -
Given an integer value n, enumerate all prime numbers from 1 to n (exclusive) and return the list with the enumeration.
Example 1:
Input: 1
Output: []
Explanation: 1 is not a prime number
Example 2:
Input: 23
Output: [2, 3, 5, 7, 11, 13, 17, 19]
Constraints:
- n >= 1
- Valid Sudoku -
Given a 9x9 sudoku board, return true if it is valid, return false otherwise.
An Example Valid Board:
Note:
A sudoku board is valid if each respective row, column, & subgrid contains unique numerical values. A duplicate value in a row, column, or 3x3 subgrid invalidates the whole board.
0 denotes an empty cell
- Spiral Traversal of A Matrix -
Given a two-dimensional matrix with m rows and n columns (m x n matrix), return its spiral ordering starting from the top left of the matrix (row 0, col 0).
Example 1:
Input:
[
[ 1, 2, 3],
[ 4, 5, 6],
[ 7, 8, 9]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
[1,2],
[3,4],
[5,6],
[7,8]
]
Output: [1,2,4,6,8,7,5,3]
Example 3:
Input:
[
[1],
[2],
[3],
[4]
]
Output: [1,2,3,4]
Example 4:
Input:
[
[1,2,3,4],
[5,6,7,8]
]
Output: [1,2,3,4,8,7,6,5]
Constraints:
0 <= m <= 100
0 <= n <= 100
- Count Subarrays That Sum To K -
Given an array of integer arr and an integer value k, return the total amount of unique, contiguous, subarrays that sum to k in arr.
Example 1:
Input: [1, 0, -1, 1] k = 0
Output: 4
Explanation: 4 subarrays sum up to 0
i j
[1, 0, -1, 1] [1,1]
[1, 0, -1, 1] [0,2]
[1, 0, -1, 1] [1,3]
[1, 0, -1, 1] [2,3]
Example 2:
Input: [3, 7, -4, -2, 1, 5] k = 3
Output: 2
Explanation: 2 subarrays sum up to 3
i j
[3, 7, -4, -2, 1, 5] [0,0]
[3, 7, -4, -2, 1, 5] [1,2]
Constraints:
- The array will not be null or empty (len(arr) > 0)
Bravo! As you have struck off your first data structure and are on the right track for heading for the next one. The idea is simple — Hunt the data structures one at a time, master all of them individually, and finally, infuse them together for solving the toughest problems with ease.
We believe our expedition on arrays must have helped you in some way and raised the bar for your learning and programming abilities. But, it is natural to be gobsmacked or perplexed while solving these problems for the first time.
Over the years, we have been exceptionally successful in building a community of programmers on our YouTube channel. With a massive following of 183k, our mentors have inculcated a strong sense of ownership and dedication to Back to Back SWE. Become a part of our community and start learning with us — https://bit.ly/3teelfS
Back to Back SWE is an all in an all-in-one platform with high-quality videos, problem statements, solutions, and tips. Therefore, we recommend you subscribe to our DSA course which has amazing content modules and world-class mentors for explanations and clearing your doubts.
Join our free 5-day mini-course for pure technical content and in-depth training.
-Team Back To back SWE