Solution to Codility lesson2-exercise1 Frog River One problem, link to Codility problem and complete solution at the end of the post.
Definitions:
Problem:
Define a function solution with input X and A, such that solution returns the minimum index of A where all elements of the sequence
, has appeared, if there isn’t such index, the function should return -1.
- Expected worst-case time complexity is O(N);
- Expected worst-case space complexity is O(X), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
Analysis:
The strategy here is to count the first appearance of every element of the sequence, to accomplish that we’ll use an array with size (X + 1), that will mark at index i the appearance of a leaf at position i , and a variable to count the first appearance.
7 8 9 |
# Counts the appearance of leaves at every position from the 1 to X count = [0] * (X + 1) total = 0 |
Then we visit every element of A, until we reach a total of X, meaning that we have a leaf at every position from 1 to X.
11 12 13 14 15 16 17 18 19 20 |
for k in xrange(N): # If it's the first time that the leaf appears at position A[k] adds one to total if count[A[k]] == 0: total += 1 # If there is a leaf in every position from 1 to X, returns the current array index if total == X: return k # Marks the position A[k] with a leaf count[A[k]] = 1 |
The worst case scenario here, it’ll be if we have to visit every element of A, to find our solution, giving a total time complexity of O(N).
For the space complexity, we’ll have O(X), because of the count array, since its size depends on the value of X.
Complete Solution:
1234567891011121314151617181920212223
# Name FrogRiverOne# Link https://codility.com/demo/take-sample-test/frog_river_one/ def solution(X, A): N = len(A) # Counts the appearance of leaves at every position from the 1 to X count = [0] * (X + 1) total = 0 for k in xrange(N): # If it's the first time that the leaf appears at position A[k] adds one to total if count[A[k]] == 0: total += 1 # If there is a leaf in every position from 1 to X, returns the current array index if total == X: return k # Marks the position A[k] with a leaf count[A[k]] = 1 return -1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
# Name FrogRiverOne # Link https://codility.com/demo/take-sample-test/frog_river_one/ def solution(X, A): N = len(A) # Counts the appearance of leaves at every position from the 1 to X count = [0] * (X + 1) total = 0 for k in xrange(N): # If it's the first time that the leaf appears at position A[k] adds one to total if count[A[k]] == 0: total += 1 # If there is a leaf in every position from 1 to X, returns the current array index if total == X: return k # Marks the position A[k] with a leaf count[A[k]] = 1 return -1 |
Time Complexity O(N)
Space Complexity O(X)
One thought on “Codility – Frog River One”