Medium coding problems and how to approach them in JavaScript
If you enjoyed understanding more about modeling logic around easy coding problems, you can be assured that another level exists. When thinking in this complex format, the scale of time and space evolve as the program, data, and solution adapt to increase the effectiveness of the software.
When building skills in code comprehension, performance, and efficiency it is an optimization technique to start big and work small, these understandings appear more frequently in challenging problems, which makes them worthy of practice.
Rehearsing the problem
As mentioned in the easy guide, we need to start looking at the problem from varying perspectives, there is a degree of balance to how closely we look at the problem, moving our view around to make sure it is fully considered. There will be primary, secondary, and tertiary layers we focus on and I will point them out to highlight moving up and down this microcosm of technology stack.
For example, let us start with the following LeetCode interview sample question and examples of the output:
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,_,_]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
// https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
From the problem, we can see that we will need to sort the array from a parameterized input, in place (without returning a new array), while reducing the integer indices to a maximum of two duplicates total in occurrence.
We again prepare a to-do list, here in practice which will allow us to condition our brains to think this way in the moment, and in the future work without these steps, if required.
//// nums is an array of duplicate numbers [0,0,0,1,1,1,2,2,2,3,3,3]
//// the required output is the parameterized array in a reduced variant with less duplicates (2 at maximum)
// 1. the array (nums) needs to be evaluated
// 2. the numbers of the array need to be reduced
// 3. the numbers from the parameter array need to be stored
// 4. the array needs to be reduced in place
// 5. after evaluation the store needs to be used to reduce the output
// 6. the final value needs to be stored in the parameter array
Coding the todos
Working through this problem while in the moment is acknowledgeably different than reflecting on it. These to-do considerations may become apparent as you work through implementing the solution.
Find enjoyment in the task by creating notes as comments throughout, and do not be discouraged when having to work back up the lines of code to solve for later lines.
I often find that when there is no requirement to directly return the result as a constant, the for each method is the least cognitively expensive (less rewriting and tinkering) through its simplicity and efficiency.
//// nums is an array of duplicate numbers [0,0,0,1,1,1,2,2,2,3,3,3]
//// the required output is the parameterized array in a reduced variant with less duplicates (2 at maximum)
nums.forEach((num) => {
})
// 2. the numbers of the array need to be reduced
// 3. the numbers from the parameter array need to be stored
// 4. the array needs to be reduced in place
// 5. after evaluation the store needs to be used to reduce the output
// 6. the final value needs to be stored in the parameter array
2/3. This next task is somewhat tricky to think about and is the pivotal point of the full equation as it introduces a secondary layer and a tertiary layer that needs to be supported throughout the rest of the code.
In this step you need to use the loop over the parameter array to extract the numbers, reference the numbers to keep, and reference the numbers to remove, doing this all at once is very complex and fragile, so using a reference store is perfectly alright.
In this sense, storing all of the values in an array as they are looped over makes sense, for quickly returning those values to inform the rest of the equation. Knowing that you are using an array means now you would need a pointer within the array that differentiates the pointer from the respective numbers.
In this secondary consideration, we could use 0 and 1 which would be an alright point number system to reference, but reusing the provided numbers later is common in Object Oriented Programming (OOP). For the numbers to be reduced it is easier to use null as the pointer for a just-in-case type of consideration that retains the initial data.
As you work through this you may also realize that in addition to the marker and number retention store, there is a requirement to refer to these pointers based on their duplicity. There are many ways to do this, and in some cases, you may prefer to use an object to do this, but since we are using a pointer, we can condition the values retained and nullified with an if…else statement.
Finally for the tertiary consideration, when building the condition we need to streamline the evaluation of duplicates to catch duplicates. We know that this array is going to be evaluated index by index and corrected before the full function finishes, so we can use that naive logic as padding within the array. We can assume that although there may be one or a first occurrence, there may also be a second occurrence, however, the index and frequency of occurrence are unimportant to the result.
领英推荐
Through this lens, we can use a simple method for the first occurrence, the includes method will detect if our store array has already accounted for the number, if that is false, we know that is the first occurrence of the number and store it.
Adding on to this condition, we need to account for numbers where their first occurrence may already exist, but we also need to evaluate if this number has two representations stored based on the problem set. For this, we can use the indexOf and lastIndexOf methods, if those indices are equal (the same) then we know that this number has only been accounted for once and can account for it now, the second time.
//// nums is an array of duplicate numbers [0,0,0,1,1,1,2,2,2,3,3,3]
//// the required output is the parameterized array in a reduced variant with less duplicates (2 at maximum)
const arr = []
nums.forEach((num) => {
if(!arr.includes(num) || arr.indexOf(num) === arr.lastIndexOf(num)){
arr.push(num)
} else {
arr.push(null)
}
})
// 4. the array needs to be reduced in place
// 5. after evaluation the store needs to be used to reduce the output
// 6. the final value needs to be stored in the parameter array
4/5. We have now evaluated the parameterized array, stored the information about the condition of each index, and sorted the various degrees of its enumeration in the temporary store constant. The next step is to use the temporary constant array to infer and reduce the parameterized array.
Now that we have the data prepared, again we use forEach to loop, instead now over our temporary store array to inform the items we need to remove from both the temporary and parameter array. We can set the element we are looping over to receive the temporary value and extract the index of that value, through the callback function to match the index of the original array.
We can see now, the value of matching the store to the data type we used, this reduces the complexity of realigning the references and utilizing the values efficiently. As we iterate through the store array we use the null pointer to inform which values to remove from both arrays, to reduce all values down to their return ready value.
As we work through the array indices, the splice method serves as one of the few ways to augment the content of the arrays without updating them in a way that would require an external change.
//// nums is an array of duplicate numbers [0,0,0,1,1,1,2,2,2,3,3,3]
//// the required output is the parameterized array in a reduced variant with less duplicates (2 at maximum)
const arr = []
nums.forEach((num) => {
if(!arr.includes(num) || arr.indexOf(num) === arr.lastIndexOf(num)){
arr.push(num)
} else {
arr.push(null)
}
})
arr.forEach((num, i) => {
if(num === null){
arr.splice(i, 1)
nums.splice(i, 1)
}
})
// 6. the final value needs to be stored in the parameter array
6. As we are working through these todos, we have to be very careful about what we do in shaping the inbound parameter array (nums). You will encounter this yourself, that these values can be modified in a way that augments their ability to be returned and meet the criteria of the problem.
Through the work we have established these values will acceptably evaluate and return the array as instructed by the coding problem. The nums array works like a classic math machine where the in parameter is adjusted or transformed through the process to the out parameter.
In the LeetCode runtime, there are restrictions on processing and efficiency, you will notice this and in some functions what may work in the Node.js runtime, may need some repetition. In this solution, I replicated the splicing loop introduced in step 4/5 to remove any leftover values remaining due to these constraints.
//// nums is an array of duplicate numbers [0,0,0,1,1,1,2,2,2,3,3,3]
//// the required output is the parameterized array in a reduced variant with less duplicates (2 at maximum)
const arr = []
nums.forEach((num) => {
if(!arr.includes(num) || arr.indexOf(num) === arr.lastIndexOf(num)){
arr.push(num)
} else {
arr.push(null)
}
})
arr.forEach((num, i) => {
if(num === null){
arr.splice(i, 1)
nums.splice(i, 1)
}
})
arr.forEach((num, i) => {
if(num === null){
arr.splice(i, 1)
nums.splice(i, 1)
}
})
arr.forEach((num, i) => {
if(num === null){
arr.splice(i, 1)
nums.splice(i, 1)
}
})
Deploying the theorem
As you move on to more challenging problems, more data, and greater transformations, these points in addition to knowing the language dynamics become ever-important. You will find that in performing these exercises, working with these habits, and reading documentation your ability to solve these problems improves.
You can find my solution to the ‘Remove Duplicates from Sorted Array II’ problem on LeetCode.
This series of loops can scale and process data quite simply, from hundreds to thousands to millions. You can see this through the test cases, in Leetcode, but the furthest assumption that we can make is that in the real world, these functions may face less reliable data. When working these lines into a software application, considerations for handling exceptions in data can be applied with promises and async methods.
In application, an example of the function may look something like the one below, where this can become a reusable function for reducing duplicate values:
You can take these ideas and apply them to your work, change them, shape them, and use them to build your own. Every developer has their style, there are many solutions and algorithms for every problem.
Creativity leads to new patterns and ideas, but can also lead to slower code and bugs, so it takes mindfulness to achieve efficiency and test experimental features adequately.
Working in best practices allows for familiarity and reliability in code, often defined by the language and framework that developers can work with and in your code.