Algorithms : A Beginner's Attempt and Reflection

As someone new to algorithm problems, seeing a big paragraph of words for a math problem can seem kind of intimidating. Here's an example of such a problem I came across only a week into practicing much simpler problems. Feel free to take a crack at it before having a look at my process:

Answer a Query
Imagine a length-N array of booleans, initially all false. Over time, some values are set to true, and at various points in time you would like to find the location of the nearest true to the right of given indices.
You will receive Q queries, each of which has a type and a value. SET queries have type = 1 and GET queries have type = 2.
When you receive a SET query, the value of the query denotes an index in the array that is set to true. Note that these indices start at 1. When you receive a GET query, you must return the smallest index that contains a true value that is greater than or equal to the given index, or -1 if no such index exists.
Input
A list of Q queries, formatted as [type, index] where type is either 1 or 2, and index is <= N
1 <= N <= 1,000,000,000
1 <= Q <= 500,000

Output
Return an array containing the results of all GET queries. The result of queries[i] is the smallest index that contains a true value that is greater than or equal to i, or -1 if no index satisfies those conditions.
Example
N = 5
Q = 5
queries = [[2, 3], [1, 2], [2, 1], [2, 3], [2, 2]]
output = [-1, 2, -1, 2]
The initial state of the array is [false, false, false, false, false].
The first query is GET 3, but no values in the array are true, so the answer is -1.
The second query is SET 2, so the value at index 2 is set to true.
The new state of the array is [false, true, false, false, false].
The third query is GET 1, and the index of the true value nearest to 1 (to the right) is 2.
The fourth query is GET 3, but no values to the right of index 3 are true.
The fifth query is GET 2, and the value at index 2 is true.

If, like me, you're new to problems like this, it can be hard to decide where the code for something like this would even start. When lost, I find it easiest to verbalize the needs of the problem before coding them.

Input is two arrays, one starts out always the same (repeating array of "false", initially) and the other one, "queries", performs the operations to give us the output array.

The output array is correlated to the "queries" array, but doesn't have to match it in length.

We perform one of two actions based on the first value of a query.

This seemed like enough to get started, so lets begin with setup. with two arrays and a function that "SETs" or "GETs". Since our output doesn't directly match anything we will start empty and add to it in our function:

const queries = [[2, 3], [1, 2], [2, 1], [2, 3], [2, 2]]
const testArray = [false, false, false, false, false]
const outputArray =[]
queries.forEach(element=>setOrGet(element))

So we have the beginning and endpoint. setOrGet needs to look at the first element of the inner array for the two separate actions

function setOrGet(innerArray){
if (innerArray[0] === 1){
//do one thing
}
if (innerArray[0] === 2){
//do the other thing
}}

We have to be careful going forward because the problem mentions:

Note that these indices start at 1.

But javascript array indexing begins at 0, so we always need to subtract 1 from the index provided. Now to add the "set" functionality, when the first element is equal to 1.

function setOrGet(innerArray){
if (innerArray[0] === 1){
testArray[innerArray[1]-1]= true
}
if (innerArray[0] === 2){
findNextTrue(innerArray[1]-1,testArray)
}}

In order to keep setOrGet concise, I made a separate function for "GET", where we are finding the next element that reads true. To do this we pass the element that we start at, and the array we are searching. I used a for loop, starting at the element, checking each for true. When a true is found I push the index (+1) to the output (we also return to break the loop and avoid pushing further elements). If no true is found, -1 is added instead.

function findNextTrue(start, array){
for(index = start; index<array.length;index++){
if (array[index]){
outputArray.push(index+1)
return
}
}
outputArray.push(-1)
}

And it works! Full solution can be seen here.

But can it be better? In this first go at the problem, the worst case scenario would repeatedly iterate over the entire N-length array of booleans, that can be up to a billion entries long. If _queries _is the maximum of 500,000 and every query is GET1, denoted as [2,1], this solution will take 5E14 operations (since without any SET operations, it will iterate all 1 billion items 500,000 times). Writing out this blog and explaining my process has already had me thinking about more efficient ways to handle this. Perhaps we have some way to keep track of where the true values are outside of the array of booleans. It is nice to see how my though process evolves in as little of a time that it has been since I started javascript 6 weeks ago (and algo problems 3 weeks ago), so this will definitely be something I revisit.

I do want my fellow beginners to keep in mind that reaching a point where it works at all is the first step before optimization.