DATA STRUCTURES
AND ALGORITHMS
ARRAY
AGENDA
What is Array
Disadvantages
Advantages
What is 2d Array
Exercise (Practice Question)
WHAT IS
ARRAY?
WHAT IS ARRAY ?
• It’s a data structure
• Its collection of Data
• Its fix sized collection of data
• Its fix sized collection of similar typed data
• Its continuous fix sized collection of similar typed
data
• Most widely known data structure in world
• Arrays are zero-indexed in programming
languages, meaning the first element is accessed
using index 0.
• So, if size of array is 10 then its n-1. Meaning 9th
index is last item in array
IT IS A CONTINUOUS STREAMED
COLLECTION OF FIXED SIZE &
SIMILAR TYPED DATA
ADVANTAGES
AND
DISADVANTAGE
S
Advantages
• Direct access: Arrays allow random access to
elements via index, which makes access time
effi cient (O(1)).
• Memory locality: Since elements are stored in
contiguous memory locations, arrays benefit from
cache locality, which speeds up access in practice.
ADVANTAGES
AND
DISADVANTAGE
S
Disadvantages
• Fixed size: Arrays have a fixed size once
declared, so their size cannot be changed
dynamically (in static arrays).
• Costly operations: Inserting or deleting an
element in the middle of an array can be
expensive (O(n)), as it requires shifting elements.
TIME
COMPLEXITY
ARRAY
Time Complexity
• Access: O(1)
• Search: O(n) for linear search, O(log n) for binary
search in sorted arrays
• Insertion: O(n) (in the worst case, when shifting is
needed)
• Deletion: O(n) (when shifting is needed)
DYNAMIC
ARRAYS
In many languages, dynamic arrays (like Python's
list, C++'s vector, C# list or Java's Array List)
automatically resize when elements are added or
removed. These offer more flexibility compared to
static arrays.
COMMON
ARRAY
PROBLEMS
• Reverse an array
IN
DSA
• Find the largest/smallest element in an array
• Merge two sorted arrays
• Find duplicates in an array
• Rotate an array
• Kadane’s algorithm (for maximum subarray sum)
COMMON
ARRAY
PROBLEMS IN
• Kadane’s Algorithm – Find the maximum
DSA
subarray sum
• Array Rotation – Rotate an array to the left or
right by a given number of positions
• Find Duplicates in an Array – Detect and
handle duplicate elements
• Two Sum Problem – Find pairs of elements that
sum up to a given value
• Reversing an Array – Reverse the elements in
KADANE’S
PROBLEM
public int kadaneAlgorithm(int[] arr) {
int currentSum = arr[0];
int maxSum = arr[0];
// Traverse through the array starting from the second
element
for (int i = 1; i < arr.length; i++) {
// Get Current Sum of subarray to compare with current
max
currentSum = Math.max(arr[i], currentSum + arr[i]);
// Update maxSum if currentSum is greater
if(currentSum > maxSum)
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
KADANE’S
PROBLEM
EXERCISE
• int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
• Maximum Sum of subarray should be
{4, -1, 2, 1} which is 6
• Try at your home and bring code in next class
2D ARRAY
• Just like array but 1 more dimension
• If we consider array as 1D as its linear and has 1 row
with continuous data (fixed sized)
• 2D has column as well.
• Just like Matrix in mathematics
• Array of size 2,2 means
• In Java we declare like this
1. int[][] array = new int[rows][columns];
//uninitialized
2. int[][] array = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
//initialized
ANY
QUESTION ?
15
THANK YOU
