DEV Community: Angela F.

Leetcode 150 | Day 5: Best Time to Buy and Sell Stock - Naive vs. Optimized

Angela F. — Sun, 21 Jun 2026 23:44:16 +0000

Leetcode 121: Best Time to Buy and Sell Stock

Leetcode 121 asks us to determine the best time to buy and sell stock from an input array prices, where each index represents a day and the value stored at that index is the cost of stocks on that day. This problem is tagged as Dynamic Programming, but I'd argue it has a greedy element to it. The choice we need to make essentially requires the question, "If I sell today, how much profit have I made, and is that the best I could have done?" We make decisions locally at each iteration of the loop, and this leads to an optimal solution.

The problem constraints:

You can choose to buy on any single day, and you must sell on a different day in the future.
If it is not possible to achieve a maximum profit, you must return 0.
1 <= prices.length <= 10^5 - the length of our input array is capped at 100,000 indexes
0 <= prices[i] <= 10^4 - prices are capped at 10,000
For both approaches we will use the following value:

- `prices = [7, 1, 5, 3, 6, 4]`

Approach 1: Naive (Brute Force)

The naive or brute force approach requires us to check every possible buy/sell combination in order to find the optimal set of days, resulting in an O(n²) time complexity.

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let max = 0;

    for (let i = 0; i < prices.length; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            let profit = prices[j] - prices[i];
            if (profit > max) {
                max = profit;
            }
        }
    }

    return max;
};

In our example we have 6 days, so roughly 36 checks, not a big deal. However:

1,000 days is approximately 1,000,000 checks
100,000 days is approximately 10,000,000,000 checks At that scale, the naive approach becomes impractical and results in this error.

The test results reflect this, 203 cases passed, but 9 failed. The failed cases are likely larger inputs where the number of checks becomes too costly.

Approach 2: Optimized (For Loop)

Tracing [7, 1, 5, 3, 6, 4]:

This approach uses two variables, minPrice and maxProfit, to track the lowest price seen so far and the best profit found so far, in one pass.

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;

    for (let i = 0; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else if (prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice;
        }
    }

    return maxProfit;
};

Let me show you how.

We begin by initializing minPrice to Infinity. Ultimately, we want to find the day where we can purchase the stock for the lowest price, and sell for the highest price. Initializing minPrice to infinity means whatever value sits in prices[0] will be stored in minPrice on the first loop iteration. The second variable, maxProfit, is initialized to zero, since no transaction has happened yet, so there's no profit to speak of at the start.

The for loop header is standard. We initialize i to 0, we continue looping through prices while i is less than the length of prices, and we increment by 1 each time through.

Once inside the loop, we enter an if/else if condition. The if statement asks if the value at prices[i] is less than the current minPrice. If it is, we update minPrice to that value. If not, we move to the else if clause, which asks a different question:

prices[i] - minPrice > maxProfit

This equation is really asking, "if I sold today, would that beat the best profit I've found so far?"

Profit, if we sold today, is defined as:

prices[i] - minPrice

This result has three possible outcomes:

prices[i] - minPrice < maxProfit → selling today would still be worse than our current best, so we leave maxProfit untouched.
prices[i] - minPrice == maxProfit → selling today ties our current best, so there's nothing to update.
prices[i] - minPrice > maxProfit → selling today beats everything we've found so far, so this becomes our new best.

Here's a table showing the value of maxProfit at each stage of the for loop:

Whenever prices[i] - minPrice > maxProfit is true, we update maxProfit. Once the loop has gone through every day in the array, we return that final maxProfit value as the answer.

Conclusion

I think we have a clear winner here. While technically both approaches are valid, the naive approach times out in Leetcode, and realistically wouldn't scale well in a real world approach anyways. The optimized approach only needs to go through the array one time which leads to an O(n) time complexity, and since we aren't creating any additional data structures to solve this - space complexity is O(1).

Leetcode 150 | Day 4: Majority Element - Naive vs. Optimized

Angela F. — Wed, 17 Jun 2026 19:49:36 +0000

Leetcode 169 asks us to identify the majority element in a given array. The majority element is defined as the element that appears more than n / 2 times. We are told that we can assume such an element always exists.

For both approaches we will use the following value:

nums = [2, 4, 2, 2, 4, 4, 4]

Approach 1: Naive (Frequency Map)

This approach uses a Map to count the frequency of each element in the array.

function majorityElement(nums) {
  const counts = new Map();

  for (const num of nums) {
    counts.set(num, (counts.get(num) ?? 0) + 1);
  }

  for (const [num, count] of counts) {
    if (count > nums.length / 2) return num;
  }
}

Our first step is to create the Map which will serve as our frequency map.

const counts = new Map();

The next step will require the use of a for loop. We will loop through the input array nums and count the number of occurrences of each value, writing that as a key/value pair to our frequency map, counts. The key will be the element from nums, and the value will be the frequency of times it appears.

for (const num of nums) {
  counts.set(num, (counts.get(num) ?? 0) + 1);
}

This for loop works by looking at each element in nums and calling .set() to store a value. The value that ends up being set depends on what .get() returns. Here's how .get() works:

We attempt to get the current count for this number from counts. There are only two possible outcomes - either we have seen this number before, or we haven't:
- If we have seen it before, .get() returns its current count and we increment by 1.
- If we haven't seen it before, .get() returns undefined. The ?? operator (nullish coalescing) catches that and defaults it to 0, then we increment by 1 to initialize the count.

The next step involves another for loop. Because this loop is separate from the first rather than nested inside it, we are still O(n) overall - two sequential O(n) loops add up to O(n), not O(n²).

for (const [num, count] of counts) {
  if (count > nums.length / 2) return num;
}

In this for loop we iterate over our frequency map's key/value pairs one by one and compare each frequency to nums.length / 2.

Using our example array:

nums = [2, 4, 2, 2, 4, 4, 4]

counts would look like this:

counts = [[2, 3], [4, 4]]

We compare the value in the first key/value pair, which is 3, to nums.length / 2:

3 > (7 / 2) -> 3 > 3.5 = FALSE

We then perform the same operation on the next key/value pair:

4 > 7 / 2 -> 4 > 3.5 = TRUE

Once we find a value that returns true we know this is our majority element, and we return num.

Time complexity: O(n)

Two sequential loops, each O(n). Two separate O(n) loops add up to O(n), not O(n²).

Space complexity: O(n)

The Map grows proportionally to the number of unique elements in the array.

Approach 2: Optimized (Boyer-Moore Majority Vote Algorithm)

The Boyer-Moore Majority Vote Algorithm, developed by Robert S. Boyer and J Strother Moore in 1981, finds the majority element in a sequence using linear time and constant memory - making it a natural fit for this problem.

function majorityElement(nums) {
  let candidate = null;
  let count = 0;

  for (const num of nums) {
    if (count === 0) candidate = num;
    count += num === candidate ? 1 : -1;
  }

  return candidate;
}

Step 1

We begin by initializing a variable candidate - this is our current best guess for the majority element, and we initialize it to null.

let candidate = null;

We initialize a second variable count. This variable acts as a confidence meter for our current candidate.

let count = 0;

Step 2

We initialize a for loop to iterate through each element of the nums array.

for (const num of nums) {
}

Step 3

The logic that goes inside the for loop:

if (count === 0) candidate = num;
count += num === candidate ? 1 : -1;

If count equals 0, we reassign candidate to the current value of num. This is because a count of 0 means we have zero confidence in our current candidate, so we replace it with the number we're looking at right now.

Then we update our confidence meter. If the current number matches our candidate, count goes up by 1. If it doesn't match, count drops by 1. Every time we see our candidate again we grow more confident. Every time we see something different, that confidence takes a hit.

This took a moment for me to understand. Here is a quick explanation and a table that should help make the concept more concrete.

Using our example array from earlier:

nums = [2, 4, 2, 2, 4, 4, 4]

The easiest way to explain how we always end up with the correct answer is to think of the elements - 2 and 4 - as opposing teams. For every element 2, there is an element 4 to cancel it out. Since 4 is our majority element, there are not enough 2s to cancel out all of the 4s.

2	4
2	4
2	4
MAJORITY ELEMENT	4

Since each pair of elements cancels each other out, and we are guaranteed that a majority element exists, it will always be the value that has no pair that will be our majority element.

Here is a step by step breakdown:

num	count === 0?	candidate	count
2	yes	2	1
4	no	2	0
2	yes	2	1
2	no	2	2
4	no	2	1
4	no	2	0
4	yes	4	1

Return 4. Correct.

Time complexity: O(n)

One pass through the array.

Space complexity: O(1)

Just two variables regardless of input size. No additional data structures needed.

Conclusion

Both approaches work fine, are pretty straightforward, and have a time complexity of O(n). However, the second approach has a space complexity of O(1). The reason for this is that this approach doesn't need a Map to determine the majority element - it can do everything using just two variables. So while Approach 1 will work fine in most cases, Approach 2 will scale significantly better.

...Day 5 coming soon

Leetcode 150 | Day 3: Remove Duplicates From Sorted Array - Naive vs. Optimized

Angela F. — Wed, 10 Jun 2026 16:56:20 +0000

Leetcode 80: Remove Duplicates II

Leetcode 80 asks us to modify a sorted array so that each unique element appears at most twice. We are to preserve relative order and store the result in the first part of array nums. The first k elements of nums will hold the result, and beyond k it does not matter what values may have been left behind. Lastly, this must be accomplished by modifying the input array in-place, without allocating any extra space.

I chose to do a writeup on this problem because it's the first time I've run into the possibility that there really isn't a feasible naive approach that respects all of the restrictions put in place - namely, the requirement of modifying in-place. I tried using splice() to shift elements out of the array while tracking position with a single pointer. However, using splice() and subsequently having to decrement the pointer with i-- doesn't work in the case of three or more consecutive duplicates. It will skip a value for the same reason outlined in Day 2. There was an identical issue I ran into there, and it is explained here Day 2 Remove Element. It may not be worth the time to continue digging around, but I am curious whether there does exist a naive approach that respects the restrictions completely.

While it's true the naive approach fails the restrictions laid out in the problem - even if that weren't the case, I'd still argue against it. The time complexity is the same as the optimized approach, but as you'll see below, the difference in readability is significant.

For both approaches we will use the following array:

nums = [1, 2, 3, 3, 4, 4, 4]

Approach 1: Naive (Nested For Loop)

Solution:

var removeDuplicates = function(nums) {
    let counts = [];

    for (let i = 0; i < nums.length; i++) {
        if (counts.length === 0 || counts[counts.length - 1][0] !== nums[i]) {
            counts.push([nums[i], 1]);
        } else {
            counts[counts.length - 1][1]++;
        }
    }

    let idx = 0;
    for (let [num, count] of counts) {
        let timesToAdd = Math.min(count, 2);
        for (let i = 0; i < timesToAdd; i++) {
            nums[idx++] = num;
        }
    }

    return idx;
};

This approach works in two passes. First, it builds a counts array that tracks how many times each number appears consecutively. Each entry is a pair: [number, count]. Then it loops over counts, writes each number back into nums at most twice using a nested loop, and returns the final index as k.

It gets the job done. But it requires an extra array, and the logic is spread across two separate loops with a nested loop inside the second. Compare that to what follows.

Time complexity: O(n)

Two passes through the data, but each is O(n). The nested loop runs at most twice per element, so it doesn't change the overall complexity.

Space complexity: O(n)

The counts array grows with the input. This is what disqualifies it - the problem explicitly requires O(1) extra memory.

Approach 2: Optimized (Two Pointers)

Solution:

var removeDuplicates = function(nums) {
    let slow = 2;

    for (let fast = 2; fast < nums.length; fast++) {
        if (nums[fast] !== nums[slow - 2]) {
            nums[slow] = nums[fast];
            slow++;
        }
    }

    return slow;
};

This approach is comparatively more straightforward, and less code. We start the algorithm by pointing both the slow and fast pointer to index 2. Why 2? Because we can make two assumptions here - only one can be true, and both are acceptable per the problem description.

Assumption 1: Both index 0 and index 1 hold the same value. This is allowed. Assuming it's true means we can skip those positions and iterate over a smaller portion of the array.

Assumption 2: The elements at index 0 and 1 are unique values. Also allowed. Same result - we skip ahead and iterate over less.

Perhaps it can be argued that the time saved here is nominal. But it can also be said, why not?

Once we've entered the for loop and hit the if statement, the condition checks whether the value at nums[fast] is the same as the value two positions behind slow. If it is, that means we already have two of this value written into the result - adding another would violate the restriction. So we skip it. If it's different, we write nums[fast] to nums[slow] and increment slow. The for loop handles advancing fast automatically at the start of each iteration.

Step 1.

Both slow and fast begin at index 2. We check whether nums[fast] equals nums[slow - 2]. nums[2] is 3 and nums[0] is 1. They are not equal, so we write 3 to nums[slow] and increment slow to 3.

Step 2.

fast advances to index 3. nums[3] is 3 and nums[slow - 2] is nums[1], which is also 3. They are equal - this would be a third consecutive 3, which violates the restriction. We skip. slow stays at 3.

Step 3.

fast advances to index 4. nums[4] is 4 and nums[slow - 2] is nums[1], which is 2. Not equal - write 4 to nums[slow]. Increment slow to 4.

Step 4.

fast advances to index 5. nums[5] is 4 and nums[slow - 2] is nums[2], which is 3. Not equal - write 4 to nums[slow]. Increment slow to 5.

Step 5.

fast advances to index 6. nums[6] is 4 and nums[slow - 2] is nums[3], which is 4. Equal - skip. slow stays at 5. fast has reached the end of the array and the loop ends.

We return slow, which is 5. The first 5 elements of nums are [1, 2, 3, 4, 4].

Time complexity: O(n)

One pass through the array. No shifting, no extra structures.

Space complexity: O(1)

Everything happens in place. No extra memory allocated.

Conclusion

Both approaches have a time complexity of O(n). However, only Approach 2 truly meets the requirements of the problem. Space complexity for Approach 1 is O(n), while Approach 2 is O(1).

Approach 1 pros:

Readable logic. Each step is explicit.
No pointer math required.

Approach 1 cons:

O(n) space. Fails the problem's constraints.
More code. Two loops, one nested.
Three loops total - two outer, one nested - means more to mentally track when reading the algorithm end to end.

Approach 2 pros:

O(1) space. Meets all requirements.
Four lines of logic once you understand the two-pointer pattern.
Scales cleanly.

Approach 2 cons:

The two-pointer pattern is less intuitive at first glance, especially the slow - 2 check.
Starting at index 2 requires understanding why the first two elements are skipped.

Sometimes we have to sacrifice readability for better time complexity, or for other reasons. This time, I don't think that's the case. We get better readability and better space complexity.

...Day 4 coming soon

Leetcode 150 | Day 2: Remove Element - Naive vs. Optimized

Angela F. — Thu, 04 Jun 2026 00:52:20 +0000

Leetcode 27: Remove Element

Leetcode 27 asks us to remove a specific value from an array. The value to be removed is passed in as a parameter to the function along with the array. Just as we did in Day 1, we will cover a naive approach and an optimized approach and discuss the trade-offs between them. I think in the end there's a pretty clear winner. Let's get started.

For both approaches we will use the following values:

nums = [1, 3, 3, 2, 4]
val = 3

Approach 1: Naive (For Loop + Splice)

This approach uses a for loop and leverages .splice() for removals.

Solution:

var removeElement = function(nums, val) {
    let k = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === val) {
            nums.splice(i, 1);
            i--;
        } else {
            k++;
        }
    }
    return k;
};

We begin by initializing a variable k to 0. We then enter the for loop. The condition is standard: create a variable i initialized to 0, continue looping while i is less than nums.length to avoid going past the end of the array, and increment by 1 each time through.

Each iteration checks one condition: whether nums[i] is equal to val. If true, we call .splice() on the array. The arguments we pass to splice are i and 1. i is the index at which we want to start removing, and 1 tells splice to remove only that one element.

We then decrement i. The reason for this took me some time to wrap my brain around, so I have included a visual below to make it concrete.

The core issue is this: when splice removes an element, every element to the right shifts one index to the left. Without i--, the loop would increment i on the next iteration and skip right over the element that just shifted in. i-- counteracts that by stepping i back, so after the loop increments it, i lands exactly where the shifted element now sits.

If nums[i] !== val, we skip the splice and increment k instead. At the end we return k, which holds the count of elements remaining after all occurrences of val have been removed.

Time complexity: O(n²)

Every splice call shifts all elements to the right of the removed index, which is O(n) on its own. If every element in the array equals val, you are doing that n times. That cost adds up fast.

Space complexity: O(1)

Everything happens in place. No extra memory is allocated.

Approach 2: Optimized (Two Pointers)

This approach uses a two-pointer technique to solve the problem. One pointer is the fast pointer i, which moves forward on every iteration. The other is the slow pointer k, which only moves forward when a value worth keeping is found.

Solution:

var removeElement = function(nums, val) {
    let k = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== val) {
            nums[k] = nums[i];
            k++;
        }
    }
    return k;
};

Here's a legend to aid clarity:

Here's how it works.

Step 1.

Both i and k begin at index 0. We check whether nums[i] === val. Since nums[0] is 1 and 1 !== 3, we write the value at nums[i] to nums[k]. We then increment both i and k.

Step 2.

Both i and k are now at index 1. We ask the same question: is nums[i] === val? It is. nums[1] is 3.

Step 3.

Since nums[i] === val, we do not write anything. We increment i but k stays put. This is the two-pointer pattern in action. k is now trailing behind i by one index position.

i is now at index 2. We ask our question again: is nums[i] === val? It is. Once again k stays put and i moves forward to index 3.

Step 4.

We ask our question again: is nums[i] === val? No. So we write the value at nums[i] to nums[k], then increment both i to index 4 and k to index 2.

Our array is now nums = [1, 2, 3, 2, 4].

Step 5.

i is at index 4, k is at index 2. We ask our question one final time: is nums[i] === val? No. We write the value at nums[i] to nums[k].

Our array is now nums = [1, 2, 4, 2, 4].

Since the problem asks us to return the count of elements remaining after removing val, we simply return k. The elements beyond index k are leftover and ignored. The first k elements are our answer.

Here is the final result:

Time complexity: O(n)

One pass through the array. No shifting, no splice.

Space complexity: O(1)

Also in place. No extra memory allocated.

Conclusion

There are genuine pros and cons to consider with each approach.

Approach 1 pros:

More intuitive to read. The logic maps closely to how most people think about removing something.
The array stays clean. All occurrences of val are actually removed, not just ignored.
Shorter code.

Approach 1 cons:

O(n²) time complexity due to repeated shifting from splice.
Mutates indices mid-loop, which requires i-- and introduces a potential bug if forgotten.
The cost of .splice() is hidden, making it easy to underestimate.

Approach 2 pros:

O(n) time. One clean pass, no shifting.
No index mutation mid-loop, simpler to reason about once the two-pointer pattern clicks.
Scales well.

Approach 2 cons:

The array is not truly cleaned up. Elements beyond k still exist in memory, just ignored.
The two-pointer pattern is less intuitive at first glance, especially for newer developers.
Returning k instead of the modified array can be confusing until you understand what the problem is actually asking for.

Both approaches solve the problem. But the time complexity difference is significant, and Approach 2 scales in a way Approach 1 simply does not. For most real-world use cases, Approach 2 is the right call.

...Day 3 coming soon

Leetcode 150 | Day 1: Merge Sorted Array - Naive vs. Optimized

Angela F. — Tue, 02 Jun 2026 00:51:37 +0000

There's been no shortage of debate lately about whether grinding Leetcode still makes sense in the age of AI. I think it does. AI is a powerful tool, but it was built by humans; which means it inherited our strengths, our blind spots, and our biases. Leaning on it entirely without understanding what's happening under the hood is a risk. A mentor once told me: those who refuse to use AI are not hireable. But neither are those who rely on it entirely. Learning deeply is how you stay on the right side of that line.

This is my journey into just that - learning deeply.

Day 1 Leetcode 88: Merge Sorted Array

This is an interesting problem. You begin with 4 pieces of data - 2 arrays and 2 integers:

nums1: a sorted array whose length equals nums1.length + nums2.length. The first m elements are valid numbers; the remaining indexes hold 0s as placeholders.
nums2: a sorted array containing only valid numbers, with a length of n.
m: the count of valid numbers in nums1.
n: the count of valid numbers in nums2.

Throughout both approaches we will use the following example values:

nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]
m = 3
n = 3

The objective is to merge both arrays into sorted order in place. Since nums1 is already sized to hold every valid element from both arrays, it's where the final sorted result will live.

Approach 1: Naive (Splice + Sort)

This solution is 2 lines of code. That's it. It's a testament to how much ES6 advanced JavaScript.

nums1.splice(m, n, ...nums2);
nums1.sort((a, b) => a - b);

Here's how it works.

We start by calling .splice() on nums1. While .splice() has many use cases, here's what each argument is doing in this context:

m: the index where we start deleting elements. Since m is the count of valid numbers in nums1, starting at index m puts us right at the first placeholder 0 - exactly where we want to be.
n: the number of elements to delete. Since n equals the length of nums2, we're deleting exactly as many placeholders as we have values to insert.
...nums2: the values we want to insert in place of the deleted elements. The ... is the spread operator, it unpacks nums2 so its values are inserted individually rather than as a nested array.

To make that concrete, without the spread operator:

nums1 = [1, 2, 3, [2, 5, 6]]  // not what we want

With the spread operator:

nums1 = [1, 2, 3, 2, 5, 6]  // ✓

Now all values live in one array. The last step is sorting. We call .sort() on nums1 and pass a compare function:

nums1.sort((a, b) => a - b);

a and b are the two elements being compared
A negative result means a comes before b
A positive result means b comes before a
Zero means they're equal

And that's Approach 1, 2 lines and Leetcode 88 is solved.

You might assume that brevity equals optimization. In terms of readability, you'd be right, as this solution is easy to scan and quick to understand. But as with most things, there are trade-offs.

Time complexity: O((m + n) log(m + n))

O(m + n) comes from iterating through both arrays once during the splice. The log(m + n) comes from calling .sort() on the combined array. Sort has to do real work, and that cost adds up as the array grows.

Approach 2: Optimized (While Loop)

This approach uses a more classic while loop. Using the same example arrays from above, here's how it works.

We begin by initializing three pointers:

i: set equal to m - 1. This points to the last valid element in nums1. Since m is 3 and arrays are zero-based, i starts at index 2.
j: set equal to n - 1. This points to the last valid element in nums2. Since n is 3 and arrays are zero-based, j starts at index 2.
k: set equal to the last index of nums1. Since nums1 has a length of m + n, and arrays are zero-based, k starts at m + n - 1.

let i = m - 1;
let j = n - 1;
let k = nums1.length - 1;

Once our pointers are initialized, we enter the while loop.

The while loop condition:

Since we'll be decrementing both i and j on each pass, we need to make sure neither pointer has gone past the beginning of its array. So we verify on each iteration that both i and j are greater than or equal to zero:

while (i >= 0 && j >= 0) {

Inside the loop:

We compare nums1[i] and nums2[j]. If nums1[i] is the larger value, we copy it to the index k is pointing to, then decrement both i and k. Otherwise, we copy nums2[j] to index k and decrement both j and k.

  if (nums1[i] > nums2[j]) {
    nums1[k] = nums1[i];
    i--;
  } else {
    nums1[k] = nums2[j];
    j--;
  }
  k--;
}

Handling remaining elements:

It's entirely possible that nums2 has more elements than nums1. If that's the case, once i reaches -1 the while loop exits, and because our condition uses &&, it doesn't matter that j hasn't reached zero yet. Any remaining elements in nums2 would be skipped.

To handle this, we add a second while loop to copy over any remaining nums2 values. Since both arrays started sorted, we can copy them directly in order:

while (j >= 0) {
  nums1[k] = nums2[j];
  j--;
  k--;
}

Because our two while loops are not nested and we never call a sort method, the time complexity improves significantly.

Time complexity: O(m + n)

Conclusion

Both approaches solve the problem, but with different trade-offs. Approach 1 is significantly easier to write and follow - two lines and you're done. But that readability comes at a cost in time complexity. Approach 2 is more involved, and more lines of code means more opportunities for bugs. But the time complexity is far better. Understanding those trade-offs is what allows us to make good decisions about which algorithmic approach to reach for.

...Day 2 coming soon

Stop Your UMAP From Moving: The Pipeline Randomness You're Missing

Angela F. — Tue, 30 Sep 2025 02:55:11 +0000

During the Spring and Summer of 2025, I was asked to create a web application to show clusters of semantically similar tweets. This was an exciting endeavor aimed at creating a dashboard to visualize how ideas spread in society.

This article is about a specific problem I solved in this project: how to get cluster plots that were consistent from run to run. To achieve this, a deep dive into understanding how randomness is used within UMAP's algorithm became necessary: how it is applied, how it helps with efficiency, its pros, and its cons. This guided me in learning how to control it, and subsequently how to create the consistent render that was asked of me.

The Paradox of Randomness in Optimization

It's sometimes interesting to learn that the concepts and strategies you think you understand, you in fact do not. Such was the case with reproducibility. I had to first resolve the fact that to create stability from run to run, I needed to understand how randomness was being used as an optimization tool.

Machinelearningmastery.com offered a ton of clarity on this:

Using randomness in an optimization algorithm allows the search procedure to perform well on challenging optimization problems that may have a nonlinear response surface. This is achieved by the algorithm taking locally suboptimal steps or moves in the search space that allow it to escape local optima.

How UMAP Uses Randomness

This image gives an excellent visual explanation of the quote above. If the algorithm did not make random choices from time to time, it would find the local minima and naturally believe it had found the most optimal solution. A move along the X-axis in either direction would appear to be a worse choice as the graph would begin to travel back up the Y-axis. However, if we employ randomness, this gives the algorithm permission to make a seemingly 'bad choice' and in doing so creates the potential for finding the global minima – which is the optimal solution in this case.

How this helps us in creating semantic clusters: UMAP needs to make random choices when it's learning from your data. It picks random starting spots for your data points, then makes random moves to create better clusters. This is the start of why we get different clusters every time we rerun our code.

Controlling the Chaos with random_state

To achieve stability with our renders, we would need to control for this. This is where random_state comes in. Behind the scenes, randomness isn't really random at all. It is still a calculated value. By using random_state = 42, as an example, 42 becomes the seed that is plugged into a mathematical formula. A formula that is rerun many times as random number generators need to produce a long sequence of numbers for UMAP to use throughout its process.

Here is how it works:

First call: plug 42 into the formula, get number A
Second call: plug number A back into the formula, get number B
Third call: plug number B back into the formula, get number C
And so on…

Since we are controlling for the very first input, and each subsequent calculation requires that the input be the output of the previous calculation, the sequence of values generated becomes predictable.

My UMAP reducer looked like this:

reducer = umap.UMAP(
    n_components=2, 
    random_state=42, 
    spread=spread, 
    min_dist=min_dist,
    n_neighbors=n_neighbors,
    metric='cosine'
)
base_coordinates = reducer.fit_transform(base_embeddings)    
return reducer, base_coordinates, base_indices

Multiple Sources of Randomness

After implementing this solution, I ran the project. Everything clustered as it should have. Then I reran the project, and much to my surprise – the data points moved. The render was not stable. There must be more points of randomness that I wasn't considering.

I spent a great deal of time scouring the internet to try and find any resource that spoke to the different points within the UMAP pipeline where randomness would occur. I came across an article entitled "Uniform Manifold Approximation and Projection in R". I performed a quick 'CTRL + F' and searched for 'randomness' to assess whether there would be anything useful here quickly. There was certainly something useful. The article states:

As shown in the section on tuning, embedding of a raw dataset can be stabilized by setting a seed for random number generation. However, the results are stable only when the raw data are re-processed in exactly the same way. Results are bound to change if data are presented in a different order.

The Root(?) of the Problem

So, what this meant for my code was a situation where my dataset was experiencing both 'change' and 'randomness' in two places:

The first was with the sample number of tweets being used at each run. I have it set to a default value of 21K tweets. At each run, it was using a random set of 21K tweets.
Additionally, I have also implemented a feature where the user can enter in 'test tweets' – this was also changing the data at each run, each time a tweet was added and each time a tweet was deleted.

But if you recall, the article specifically stated: "...the results are stable only when the raw data are re-processed in exactly the same way."

I then added a random seed here:

base_tweets_df = base_tweets_df.sample(n=max_tweets, random_state=42)

This would hopefully ensure that the sample tweets would remain consistent from run to run. After implementing the second random seed, I reran the project. And to my astonishment, the clusters no longer moved from run to run. I could now change the sample data size and rerun the project, and I would get a consistent and static render of clusters from run to run.

The Final Challenge: Dynamic User Input

The next test would be to see if my success held when adding and removing test tweets via the UI. Unfortunately, my previous success would be short-lived. Again, I would encounter data points that would move each time a tweet was added or removed.

"...the results are stable only when the raw data are re-processed in exactly the same way."

That phrase again. It was clear that every time a user inputted a test tweet or deleted a test tweet, the raw data was not being re-processed in the exact same way. UMAP was recalculating everything from scratch as it thought it had a new dataset to work with.

The Storage Room Analogy: A Mental Model for the Solution

So, the solution for this went like this. Let's say you were storing all of your holiday decorations in a storage room. And you have decided that Christmas decorations would always go in the upper right corner of the shelves. And Halloween decorations always went in the lower left corner, and Thanksgiving in the middle, so on and so forth. If this layout never changes, then when new boxes of Christmas decorations are added, instinctually they will go in the upper right corner. And that new glow-in-the-dark skeleton you got for this Halloween will naturally go in the lower left corner. These rules never change; therefore, when adding new decorations, they will always go in the same cluster of related boxes in the same location, and when you remove them, you will always be able to predictably find them.

In this image, you can see that each holiday has a designated spot for its decorations. With these spots enforced, any new boxes of Christmas decorations will naturally go in the upper right-hand corner, and Thanksgiving decorations added will naturally go in the middle. This is possible because the rules have been cached and are applied to each new box of decorations as they are added.

This was the basis for the fix. In the context of the code, the idea is identical. I would train UMAP on the exact same dataset from the embeddings file. The random seed ensured that the same dataset would be used from run to run, and the reducer would be cached so that UMAP's existing trained model could use .transform() for new tweets. So, the base dataset would always cluster the same, and as new test tweets came in and had the same reducer applied, they would always cluster in the same location as well – exactly in the same way that Thanksgiving decorations would always end up in the middle of the shelves.

Conclusion

This project has taught me quite a bit. For starters, there is nuance in machine learning that is important to consider. The primary example being that without the feature that allows the user to enter test tweets and remove them – the two random seeds likely would have solved my entire reproducibility issue alone.

I think at times it's also easy to default to 'Does this solution fix my problem?' If yes, great! – and we move on. Without diving into how stochastic algorithms work, and more importantly 'why' they have the randomness characteristic – solving this without this knowledge would have been so much more painful and time-consuming.

In the end, what started as a frustrating bug became an important learning moment. Sometimes, the most annoying of bugs end up teaching us the most.

DEV Community: Angela F.

Leetcode 150 | Day 5: Best Time to Buy and Sell Stock - Naive vs. Optimized

Leetcode 121: Best Time to Buy and Sell Stock

- prices = [7, 1, 5, 3, 6, 4]

Approach 1: Naive (Brute Force)

Approach 2: Optimized (For Loop)

Conclusion

Leetcode 150 | Day 4: Majority Element - Naive vs. Optimized

Approach 1: Naive (Frequency Map)

Approach 2: Optimized (Boyer-Moore Majority Vote Algorithm)

Conclusion

Leetcode 150 | Day 3: Remove Duplicates From Sorted Array - Naive vs. Optimized

Leetcode 80: Remove Duplicates II

Approach 1: Naive (Nested For Loop)

Approach 2: Optimized (Two Pointers)

Conclusion

Leetcode 150 | Day 2: Remove Element - Naive vs. Optimized

Leetcode 27: Remove Element

Approach 1: Naive (For Loop + Splice)

Approach 2: Optimized (Two Pointers)

Conclusion

Leetcode 150 | Day 1: Merge Sorted Array - Naive vs. Optimized

Day 1 Leetcode 88: Merge Sorted Array

Approach 1: Naive (Splice + Sort)

Approach 2: Optimized (While Loop)

Conclusion

Stop Your UMAP From Moving: The Pipeline Randomness You're Missing

The Paradox of Randomness in Optimization

How UMAP Uses Randomness

Controlling the Chaos with random_state

Multiple Sources of Randomness

The Root(?) of the Problem

The Final Challenge: Dynamic User Input

The Storage Room Analogy: A Mental Model for the Solution

Conclusion

- `prices = [7, 1, 5, 3, 6, 4]`