LESSON 146 OF 348 · LOOPING OVER ARRAY INDICES

Linear Search in Kotlin: Finding 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 Kotlin, explained

Problem overview

The function find receives an IntArray named nums and an Int named value. It returns the index at which value sits in nums, or -1 if the value isn't there. The lesson asks for O(n) time and O(1) extra space.

In the example, nums = [1, 2, 4, 5] and value = 4. The value 4 is at index 2, because nums[2] is 4, so the function returns 2. For value = 3 the result would be -1.

Approach: check the elements one by one

This is linear search. You look at the first element, then the second, and so on, stopping as soon as you find a match. If you reach the end without a match, the value isn't present.

Nothing is assumed about the order of the array, so no element can be skipped: any one of them could be the match. In the worst case, when the value is at the end or missing, you look at all n elements, which is the O(n) the lesson asks for. If the array were sorted, a faster method called binary search would be possible, but this lesson doesn't rely on order.

A loop that visits only the values, like for (num in nums), tells you whether a match exists but not where. Because the answer is a position, the loop has to run over positions, the indices.

Step by step

Loop over the indices. for (i in nums.indices) makes i take each valid position from 0 to nums.size - 1, and you read the element with nums[i].
Test each element and return the index at once. If nums[i] == value, the search is over. Returning i inside the loop ends the function immediately, so the first match wins. When the value appears several times, the function returns the lowest index.
Return -1 after the loop. The line runs only if no iteration returned, which means every element differed from value. The number -1 can never be a real index, so the caller can tell "not found" from a genuine position.

The solution in Kotlin

class Solution {
    fun find(nums: IntArray, value: Int): Int {
        for (i in nums.indices) {
            if (nums[i] == value) {
                return i
            }
        }
        return -1
    }
}

The Kotlin details behind it:

nums.indices. It is the range 0..nums.size - 1, built for you. In Kotlin the length of an array is the property size, not length. Writing nums.length is a compile error. For an empty array, indices is an empty range, so the loop body never runs.
Return from inside a loop. A return leaves the whole function, not just the loop. That is what makes the search stop early.
== compares values. For Int elements, nums[i] == value asks whether the two numbers are equal.
The function must return on every path. The final return -1 is required. The compiler can't know that the loop will find a match, and without it the function would not compile.
A built-in exists. nums.indexOf(value) does the same job and returns -1 when the value is missing. Writing the loop yourself shows how it works.

Complexity

Let n be the length of nums.

Time: O(n). The loop runs at most n times, with one comparison each. The best case is a match at index 0, which takes a single comparison. The worst case, a missing value or a match at the last position, takes n.

Space: O(1). The only extra storage is the loop variable i.

Edge cases and common mistakes

The value is missing. [1, 2, 4, 5] with value = 3 returns -1.
An empty array. The loop doesn't run, so the result is -1.
Repeated values. [7, 7, 7] with value = 7 returns 0, the first index.
Value at index 0. The function returns 0, which is a valid answer and different from -1. A caller must test for "not found" with result == -1, not with a check for zero.
Returning the element instead of the index. return nums[i] would return value itself, which is the number you already knew.
Putting return -1 inside the loop. The function would give up after the first element that doesn't match. The "not found" answer can be given only after all elements have been checked.
Unsorted input. It doesn't matter. [9, -1, 5] with value = 5 returns 2.

Testing

nums = [1, 2, 4, 5], value = 4 gives 2.
nums = [1, 2, 4, 5], value = 3 gives -1.
nums = [], value = 3 gives -1.
nums = [7, 7, 7], value = 7 gives 0.
nums = [9, -1, 5], value = 9 gives 0.

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

Start learning free