LESSON 146 OF 348 · LOOPING OVER ARRAY INDICES

Linear Search in TypeScript: Find an Index in O(n) Time

Given an array of integers nums, return the index of a given value.

If the value doesn't exist, return -1.

Example 1:

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: nums[2] is 4

Note:

Your algorithm should run in O(n) time and use O(1) space.

Hints:

We should try out each element in nums until we find one equal to value and return its index. How can we achieve this?

With a for loop, of course! We can use a variable num to iterate through the elements and an if statement to check if num == value:

for each num in nums:
	if num == value:
    # Solution found! But...

This is how we look for value in nums, but there's a problem. The problem asks us to return the index of that element, and by iterating like this we only know the value of the current element, not its index. How can we fix this?

We should use another method of iterating through an array: by indices! Let's use an index variable i to go through every index between 0 and nums.length - 1:

for i : 0 -> nums.length - 1:
	# index is i, value is nums[i]
  	if nums[i] == value:
    		return i

What if we don't have any element equal to value? Where should we return -1?

for i : 0 -> nums.length - 1:
	# index is i, value is nums[i]
  	if nums[i] == value:
    		return i

# Here:
return -1

If we reach the line with the comment, this means the for loop terminated naturally without returning any index. If we have had returned an index, we wouldn't even be executing this line of code as the program would have finished.

We have a for loop that performs exactly n iterations (where n is the length of nums), thus the Time Complexity is O(n).
The only extra space we use is the iterator variable i inside the loop, thus the Extra Space used is O(1).

Video Solution:

STEP 1 OF 3

Guided

Ctrl + Enter to check

Linear Search in TypeScript, explained

Problem overview

The method find receives an array of numbers, nums, and a number, value. It returns the index where value sits in the array, or -1 if value isn't there. For nums = [1, 2, 4, 5] and value = 4 the answer is 2, because nums[2] is 4.

The statement sets the limits: O(n) time and O(1) extra space. That fits the simplest idea: look at the elements one after another until you find the one you want.

Approach: check each position in order

This is a linear search. Start at index 0 and compare each element with value. The moment one matches, you know the answer and can return its index right away. If the loop reaches the end of the array without a match, the value isn't present, so the method returns -1.

The method needs the index, not just the value, and that's the reason this lesson uses a loop over indices. A for...of loop would give the elements, but would not tell you where you are. Counting with an index i gives you both: the position i and the element nums[i].

Linear search needs no preparation, and it works on any array, sorted or not. If the array were sorted, a faster approach like binary search could skip most elements, but that is a different lesson.

Step by step

Write the loop. Start i at 0 and run while i < nums.length. The last valid index is nums.length - 1, so the condition uses <.
Compare in the loop. Check nums[i] === value. When it's true, return i immediately: the position is found, and the loop has no more work. Because the loop returns at the first match, a value that appears several times gives its first index.
Return -1 below the loop. This line is reached only when the loop finished without returning. Since -1 can never be a real index, the caller can tell "not found" from any actual position.

The solution in TypeScript

class Solution {
    find(nums: number[], value: number): number {
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] === value) {
                return i;
            }
        }
        return -1;
    }
}

The TypeScript points to know:

Strict equality. === compares without converting types, so a stray string never matches a number. It is the usual choice in TypeScript.
Returning from inside a loop. A return ends the whole method, not just the current pass, so the remaining elements are never examined.
Types are compile-time only. The annotations on nums and value are removed from the JavaScript, so nothing stops a wrong type from arriving at run time, for example from parsed JSON. With === a mismatched type simply fails to match.
The built-in way. Arrays have an indexOf method that does the same job, [1, 2, 4, 5].indexOf(4) gives 2, and a missing value gives -1. Writing the loop yourself shows what such a method does.

Complexity

Time: O(n), where n is the length of nums. In the worst case, when the value is last or absent, the loop makes n comparisons. Finding it early stops sooner, but the bound is for the worst case.

Space: O(1). The method keeps only the index i.

Edge cases and common mistakes

The value is missing. find([1, 2, 4, 5], 3) reaches the final line and returns -1.
An empty array. The loop condition is false at once, so the method returns -1.
Duplicates. find([7, 7], 7) returns 0, the first position, because the loop returns at the first match.
Putting return -1 inside the loop. It would give up after checking only the first element, so find([1, 2, 4, 5], 4) would return -1.
Returning the value instead of the index. return nums[i] would return 4 in the example, not 2.
Using <= in the loop condition. At i = nums.length, nums[i] is undefined. That doesn't crash, but it is a wasted pass and a sign of an off-by-one error.
NaN. NaN === NaN is false, so find([NaN], NaN) returns -1. The lesson's inputs are ordinary integers, so this is only a curiosity.

Testing

find([1, 2, 4, 5], 4) gives 2.
find([1, 2, 4, 5], 3) gives -1.
find([7, 7], 7) gives 0.
find([], 1) gives -1.
find([9], 9) gives 0.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free