Intro

There’s many many different patterns to dealing with arrays problems.
Everything from brute force solutions that are O(n^2) to clever sorts and searches.
Review Arrays

Two Sum - Easy

In which an array of numbers has two values that sum up to a given target value. The naive approach is to brute force it, but if you use a hashmap of each number and its index, you can start checking if the difference of target - numbers[i] is already in that hash map and therefore you’ve hit the second number, leading to a O(n) lution.

Best Time Buy and Sell - Easy

Iterating through an array twice but in O(n)
If you need to iterate through an array twice to check for values that meet certain conditions, consider only one loop in which you check the conditions as you go through. This is done via dynamicprogramming. A a programming paradigm of sorts in which the result is found by comparing it to the previous result. Very common with problems that require recursion.
Consider this simple LeetCode problem
I’ve also done this in Python, just replace Infinity with None and Python enumerate function to iterate.

function maxProfit(prices: number[]): number {
   // Solution 2 - Math module, one loop -> O(n)
   let max_stonks = 0;
   let min_price = Infinity;
 
   for(let i = 0; i < prices.length; i++){
        const current: number = prices[i] - min_price;
        min_price = (min_price > prices[i]) ? prices[i] : min_price;
        max_stonks = (current > max_stonks) ? current : max_stonks;
   }
   return max_stonks;
};

Median of Two Sorted Arrays - Easy

Utilizes 3 while loops, the first is comparing elements until one of i and j indices reaches the end.
The other two are for the remaining elements in the other array.

Code in Java:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merged = new int[nums2.length + nums1.length];
        int i = 0, j = 0, k = 0;
 
        // add the smaller of the two numbers
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }
        // Adding the remainders to which are sorted
        while (i < nums1.length) {
            merged[k++] = nums1[i++];
        }
        while (j < nums2.length) {
            merged[k++] = nums2[j++];
        }
 
        if (merged.length % 2 == 0) {
            int mid = merged.length / 2;
            return (double) (merged[mid] + merged[mid - 1]) / 2;
        } else {
            return merged[(merged.length / 2)];
        }
    }
}

To get a hand on it try the following example using a debugger:

MedianTwoSortedArrays clssy = new MedianTwoSortedArrays();  
int[] nums1 = {1, 3};  
int[] nums2 = {2, 4};  
System.out.println(clssy.findMedianSortedArrays(nums1, nums2));

Binary Search in Array - Easy

This one’s a binarysearch classic, it does use the underlying concept of recursively searching using by comparing the middle element and checking if less or greater than target. But unlike the BST version, you’re not calling actually making a recursive call, instead you’re using two pointers.

Procedure

set left to 0 and right to n- 1, where n is the length of the array.
Set middle to be l + floor((right - left) / 2)
While left is less than or equal to right, check if the middle element is less than or greater than the target.
1. If greater, then set left to middle + 1
2. If less, then set right to middle - 1
If middle == target return middle
else return -1

 public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
 
        while (left <= right) {
            int mid = left + floor((right - left) / 2);
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            }
            else{
                return mid;
            }
        }
        return -1;
    }
}

Setting the middle pointer

We set it to L + floor((R - L) / 2) instead of (R + L) / 2 to avoid integer overflow because in some programming languages (like C++, Java, etc.), integers have a fixed maximum size (e.g., 2³¹ - 1 for a 32-bit signed integer). If L and R are both large numbers, it might overflow and cause exceptions…

Valid Anagram - Easy

anagram refers to a string that has the same specific characters as another AND the same count per character. Link
This is my “normal” and intuitive solution, however it’s not the most efficient. it’s certainly $O (n)$ at the very least, but I don’t know for certain the time complexity of the Array.sort() function in Java, nor the toCharArray() function… These play a role in efficiency. Regardless, this is a simple solution that was penned in 5min.
Code:

class Solution {
    public boolean isAnagram(String s, String t) {
       if (s.length() != t.length()) {
            return false;
        }
        
        char[] chars1 = s.toCharArray();
        char[] chars2 = t.toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        for (int i = 0; i < chars1.length; i++) {
            if(chars1[i] != chars2[i]) {
                return false;
            }
        }
        return true;
    }
}

A better and way more clever solution utilizes the fact that Characters are numerically represented in unicode .
How it works:

If lengths aren’t equal, return false.
Initialize an integer array, 26 elements.
Iterate through first string and use the index of the char within the alphabet while increment it.
Iterate through second string.
1. If value at index is 0 then return false.
2. Otherwise decrement, to account for differences.

Step 4 is where the comparisons happen, try it on paper with simple example if unsure what I mean.
Note that these solutions end up being similar time complexity wise but the second one is more memory efficient.
Code:

class Solution {
    public boolean isAnagram(String s, String t) {
       if (s.length() != t.length()) {
            return false;
        }
        
        int[] charCount = new int[26];
        for(int i = 0; i < s.length(); i++){
            charCount[s.charAt(i) - 'a'] += 1;
        }
 
        for(int i = 0; i < t.length(); i++){
            if(charCount[t.charAt(i) - 'a'] == 0){
                return false;
            }
            charCount[t.charAt(i) - 'a'] -= 1;
        }
        return true;
    }
}

And a more optimized version:

class Solution {
    /**
     * @param {string} s
     * @param {string} t
     * @return {boolean}
     */
    isAnagram(s, t) {
        if(s.length != t.length){
            return false;
        }
 
        let counts = new Array(26);
        counts.fill(0);
 
        for(let i = 0; i < s.length; i++){
            counts[s.charCodeAt(i) - 'a'.charCodeAt(0)] += 1;
            counts[t.charCodeAt(i) - 'a'.charCodeAt(0)] -= 1;
        }
        return counts.every((v) =>  v === 0);
    }
}

First Bad Version - Easy

This one’s another spin on binarysearch. Although the input is an integer n representing the number of versions, such that $1 <= v er s i o n <= n$ . We’re tasked with finding the first bad version, given an API (function) that determines if a version’s bad or not.

Breakdown

Set start to 1 and end to n.
While start < end, init mid value.
check isBad(mid):
1. If true, set end = mid
2. else start = mid
return start
This one differs than regular Binary Search because you’re trying to find the first bad version, which means moving the start till it hits the first.

Code:

public int firstBadVersion(int n) {  
    int start = 1;  
    int end = n;  
    while(start < end){  
        int mid =  start + ((end - start) / 2);  
        if(isBadVersion(mid)){  
            end = mid;  
        } else {  
            start = mid + 1;  
        }  
    }  
    return start;  
}

Ransom Note - Easy

Another simple but faster solution compared to the hashmap solution.

Breakdown

Init a 26 integer array, to represent our alphabet’s count… Very similar to Valid Anagram above!
Iterate through the magazine and count.
Iterate through the note and check if count’s greater than or equal to one.
- Decrement if yes
- return false otherwise
  // I have both ways of iterating through them using for loops for sake of flavor and diversity...
  Code:

public boolean canConstruct(String note, String magazine) {  
    if (magazine.length() < note.length()) return false;  
  
    int[] charCount = new int[26];  
    for (char c : magazine.toCharArray()) {  
        charCount[c - 'a']++;  
    }  
  
    for (int i = 0; i < note.length(); i++) {  
        if (charCount[note.charAt(i) - 'a'] >= 1) {  
            charCount[note.charAt(i) - 'a']--;  
        }  
        else return false;  
    }  
    return true;  
}

Majority Element - Easy

You’re given an array of randomized integers, often repeating more than once. And you’re asked to return the majority element, i.e. the element that appears more than $f l oor (n /2)$ times in the array. Where n is the number of elements in the array such that $1 <= n <= 5 * 1 0^{4}$

My Solution

My first intuition was, this can be solved using a hashmap. That will end up being a time and space solution because of traversing the hashmap’s key-value pairs until the majority is found. Cool, but we’re better than that, only a bit…

Breakdown

Sort the array of integers, use built-in function as it’s optimized for a simple task like this.
Init two variables, the majority and its count.
Iterate once through the sorted array while checking the conditions.
Code:

def majorityElement(self, nums: List[int]) -> int:
	if len(nums) == 1:
		return nums[0]
 
	sorted_nums = sorted(nums)
	majority = sorted_nums[0]
	count = 0
	for i in range(0, len(nums)):
		if sorted_nums[i] == majority:
			count += 1
		elif sorted_nums[i] != majority and count < len(nums) / 2:
			majority = sorted_nums[i]
			count = 1
	
	return majority

This is a a $O (n)$ time and $O (1)$ space solution.

Boyer-Moore Voting Algorithm

Now, for a smarter solution.

Breakdown

Initialize a majority variable and a count variable.
Traverse the array once:
-> If count is 0, set the majority to the current element and set count to one.
-> If the current element equals the majority, increment count.
-> If the current element differs from the majority, decrement count.
Traverse the array again to count the appearances of majority.
If the majority’s count is greater than $n /2$ , return the majority as the majority element.
Code:

def majority_element_boyer_moore(self, nums):  
    majority = -1  
    count = 0  
    for a in nums:  
        if count == 0:  
            majority = a  
        if a == majority:  
            count += 1  
        else:  
            count -= 1  
    return majority

For a thorough explanation (you need to draw it out) check this video by Greg Hogg

Meeting Rooms - Easy

This problem deals with arrays and while it can be brute-forced, it should be solved by sorting the input first!

Here’s my complex and ugly solution:

"""
Definition of Interval:
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""
 
class Solution:
    def canAttendMeetings(self, intervals: List[Interval]) -> bool:
        """Edge cases:
            len intervals is 0 or 1
            start/end times that are t < 0
        """
        length = len(intervals)
        if length <= 1:
            return True
        sorted_meetings = sorted(intervals,key=cmp_to_key(self.custom_sort))
        # scan the array of meeting times
        for i in range(length):
            # check if the start of the next meeting is before the current
            if i+1 <= length -1 and sorted_meetings[i+1].start < sorted_meetings[i].end:
                return False
        return True
 
    def custom_sort(self, a:Interval, b:Interval) -> int:
        if a.start < b.start:
            return -1
        elif b.start  < a.start:
            return 1
        else:
            return 0

Here’s a more elegant way:

def canAttendMeetings(self, intervals: List[Interval]) -> bool:
	intervals.sort(key=lambda i: i.start)
	
		for i in range(1, len(intervals)):
            i1 = intervals[i - 1]
            i2 = intervals[i]
            
            if i1.end > i2.start:
                return False
        return True

Breakdown:

Using lambda to define a the key to compare
Starts at second element not first
Checks current and previous intervals, easier bounds management
Time & Space Complexity: O(nlog⁡n)
Space complexity: O(1) or O(n) depending on the sorting algorithm.

Merge Intervals - Medium

This one builds on the previous problem, you’re determining overlaps but also merging them!
This version uses a 2D array instead where intervals[i] = [start_i, end_i].

// Highly recommend drawing a number line

Algorithm

The logic to track overlaps is the same as in Meeting Rooms
However, we need to build an output array initialized with the first element of the sorted intervals array. E.g. merged_intervals = [sorted_intervals[0]]
Then we loop through the sorted array starting from second element and check overlap with the Last appended element to the output array.
If overlap: merge the two, remove the last from the output, append the merged
Else: append interval to output
return output array

Here’s my ugly solution built on the ugly Meeting Rooms:

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        length = len(intervals)
        if length <= 1:
            return intervals
        sorted_intervals = sorted(intervals, key=cmp_to_key(self.time_sort))
 
        merged_meetings = [sorted_intervals[0]]
        for i in range(1, length):
            if sorted_intervals[i][0] <= merged_meetings[-1][1]:
                new_interval = self.merge_interval(sorted_intervals[i], merged_meetings[-1])
                print(new_interval)
                merged_meetings.remove(merged_meetings[-1])
                merged_meetings.append(new_interval)
            else:
                merged_meetings.append(sorted_intervals[i])
        return merged_meetings

And here’s a much faster solution I wrote after watching NeetCode’s explanation, it’s very similar but sorting and merging’s more efficient

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
	if len(intervals) <= 1:
		return intervals
	
	intervals.sort(key=lambda x: x[0])
	merged_intervals = [intervals[0]]
	
	for i, m in enumerate(intervals): # m is (start, end)
		last = merged_intervals[-1]
		if  m[0] <= last[1]:
			new_interval =[min(m[0], last[0]), max(m[1], last[1])]
			merged_intervals.pop()
			merged_intervals.append(new_interval)
		else:
			merged_intervals.append(m)
	return merged_intervals

Insert Interval

This problem gives you a sorted array of NON overlapping intervals and a new interval to insert into the array.
The aim is to insert the new interval while meeting conditions:

Maintain ascending order
Merge any intervals the new interval may overlap with
// To me, this shouts #BinarySearch from afar.

Algorithm

Use binary search to find the correct position where newInterval should be inserted based on its start time.
After inserting, the list is still sorted by start time.
Then we do a normal merge intervals pass:
- if the current interval does not overlap the last interval in the result, append it
- otherwise merge them by extending the end
Initialize an empty output array
Iterate through the (now sorted) intervals:
1. If output is empty or the current interval starts after the last interval in output ends: append the current interval to output
2. Otherwise (overlap exists): merge by updating the last interval’s end: output[-1].end = max(output[-1].end, current.end)
Return output

My binarysearch solution, had to fix it with an explanation for the final sweep:

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
 
        # recursive base case
        if len(intervals) == 0 or intervals is None:
            return [newInterval]
 
        start = 0
        end = len(intervals) -1 
		# binary search
        while start <= end:
            mid = start + (end - start) // 2
            if intervals[mid][0] < newInterval[0]:
                start = mid + 1
            elif newInterval[0] < intervals[mid][0]:
                end = mid - 1
            else:
                break # found the spot, don't insert, Break!
        intervals.insert(start, newInterval)
 
        merged = []
		# final sweep to check the overlaps
        for intv in intervals:
            if not merged or merged[-1][1] < intv[0]:
                merged.append(intv)
            else:
                merged[-1][1] = max(merged[-1][1], intv[1])
        return merged

Breakdown:

Build output array from the end, every new interval added
Check if overlap with last added element
- If not, append.
- Otherwise, set the end of the last interval add to be the max value instead (growing it)

Abdu's Garden

Explorer

Array Problems

Intro

Two Sum - Easy

Best Time Buy and Sell - Easy

Median of Two Sorted Arrays - Easy

Binary Search in Array - Easy

Procedure

Valid Anagram - Easy

First Bad Version - Easy

Breakdown

Ransom Note - Easy

Breakdown

Majority Element - Easy

My Solution

Breakdown

Boyer-Moore Voting Algorithm

Breakdown

Meeting Rooms - Easy

Merge Intervals - Medium

Algorithm

Insert Interval

Algorithm

Graph View

Table of Contents

Backlinks