Problem overview
The method contains receives an array of numbers, nums, and a single number, value. It returns true if value occurs anywhere in nums and false if it does not. The task rules out the built-in includes(), because the point is to write the search yourself.
For contains([1, 2, 4, 5], 4) the answer is true: the third element is 4. For contains([-1, 2, -4, 0, 10], 7) the answer is false, because none of the five elements equals 7.
Approach: look at each element until one matches
The array has no useful order, so there is no shortcut: the only way to be sure a value is absent is to check every element. This is called a linear search. You walk through the array from the start and compare each element with the target.
The key observation is that the two answers are not symmetric:
- To answer
true, one match is enough. As soon as you find it you can stop, and the elements after it do not matter. - To answer
false, you need to have seen all the elements. That conclusion can only be drawn after the loop has finished.
So the structure is a loop that returns true from the inside as soon as it finds a match, followed by a return false after the loop. If the loop ever returns, the answer was true. If it runs out of elements, nothing matched.
Step by step
- Loop over the values. The
for...ofloop hands you the elements themselves, which is exactly what you compare. The lesson calls the loop variableval, and each element ofnumsis bound to it in turn. - Compare inside the loop. If
valequalsvalue, returntrueright away. Areturninside a loop ends the whole method, so the remaining elements are never looked at. That is the early exit, and it is what makes the search stop at the first occurrence. - Return
falseafter the loop. This line is reached only when the loop has gone through every element without returning. At that pointvaluehas been compared with every element and matched none of them, so noelseis needed.
A tempting alternative is to return false in an else branch inside the loop. That breaks the method: the first element that differs from value would end the search with the answer false, even if the target appears later. The false answer has to wait until the end.
The solution in TypeScript
class Solution {
contains(nums: number[], value: number): boolean {
for (const val of nums) {
if (val == value) {
return true;
}
}
return false;
}
}
The TypeScript details worth knowing:
for...ofversusfor...in.for (const val of nums)yields the elements.for (const x in nums)yields the indices, and as strings: for[10, 20, 30]it gives"0","1","2". Usinginhere would compare the wrong things.constin the loop header. A newvalis created on every pass, soconstis allowed even though the value changes from one pass to the next.==and===. The solution uses==. With two numbers it behaves like the strict===. The difference appears only if one side is not a number at run time. TypeScript's types are erased in the JavaScript it writes, so a caller that sneaks a string in, for example through a value typedany, would seecontains([1, 2, 4, 5], "4")returntruewith==, andfalsewith===. Prefer===in code you write yourself.NaNis never equal to anything. That includes itself, socontains([NaN], NaN)returnsfalsewith this loop. The built-inincludes()would returntruefor the same input, because it uses a slightly different comparison. This does not matter for the lesson's integers.- Return type. The method returns a
boolean, and every path through it does return one. The compiler checks that the annotation matches what you return.
Complexity
Time: O(n). In the worst case, the value is last or missing, and the loop compares it with all n elements, doing a constant amount of work for each. In the best case, the first element matches and the method finishes after one comparison. Big O describes the worst case.
Space: O(1). The method uses only the loop variable. It builds no new array and does not copy nums.
Edge cases and common mistakes
- Empty array. The loop body never runs, so the method reaches
return false. That is correct: nothing can occur in an empty array. - The value appears more than once.
contains([5, 5, 5], 5)returnstrueon the first 5. The method only reports whether the value occurs, not how many times. - The value is the first or the last element. Both must be found. A loop that skips index 0, or stops one element early, fails on exactly these.
- Negative numbers and zero. They compare like any other number.
contains([-1, 2, -4, 0, 10], 0)istrue. - Returning
falsetoo early. Puttingreturn falsein anelseinside the loop, as described above, makes the method look only at the first element. - Forgetting the final return. Without the last line, the method falls off its end when nothing matches and gives back
undefinedinstead offalse. The compiler is not guaranteed to warn you, because the lessons are compiled without strict checks.
Testing
nums = [1, 2, 4, 5],value = 4givestrue.nums = [-1, 2, -4, 0, 10],value = 7givesfalse.nums = [],value = 3givesfalse.nums = [5, 5, 5],value = 5givestrue.