[Uber][LeetCode] Substring with Concatenation of All Words

Problem: You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

• For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.

Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

Example:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words. The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words.

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo", "the"]
Output: [6,9,12]
Explanation: The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"]. The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"]. The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"]

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Explanation: There is no concatenated substring.

Approach: Let's start with the simplest approach. We can take every substring of 's' of size equal to the LENGTH(words) * LENGTH(words[0]) and then see if evey word of words is in the substring or not. If yes we can push the start index of substring into result otherwise we move the start index by 1.

Now we need to see how we can do it efficiently. To do it efficiently, we can use hash maps. Basically we can store every word of words in a hash map as key and their frequency as value. We can have another hash map which will track the all the substring of size LENGTH(words[0]) in the current window. 

Current window is s[i ... i + LENGTH(words) * LENGTH(words[0])] where  i = 0 .. n - LENGTH(words) * LENGTH(words[0])

Rest you can understand by just looking at the implementation.

Implementation in C#:

    public IList<int> FindSubstring(string s, string[] words)

    {

        List<int> result = new List<int>();

        int length = s?.Length ?? 0;

        int numOfWords = words?.Length ?? 0;

        if (length == 0 || numOfWords == 0)

        {

            return result;

        }

        int sizeOfWord = words[0].Length;

        int sizeOfWords = sizeOfWord * numOfWords;

        if (length < sizeOfWords)

        {

            return result;

        }

        var wordsMap = this.BuildWordsMap(words);

        for (int i = 0; i <= length - sizeOfWords; ++i)

        {

            var tempMap = new Dictionary<string, int>();

            int count = numOfWords;

            for (int j = i; j < i + sizeOfWords; j += sizeOfWord)

            {

                string currWord = s.Substring(j, sizeOfWord);

                if (!wordsMap.ContainsKey(currWord))

                {

                    break;

                }

                if (!tempMap.ContainsKey(currWord))

                {

                    tempMap[currWord] = 0;

                }

                ++tempMap[currWord];

                if (tempMap[currWord] > wordsMap[currWord])

                {

                    break;

                }

                --count;

            }

            if (count == 0)

            {

                result.Add(i);

            }

        }

        return result;

    }

    private Dictionary<string, int> BuildWordsMap(string[] words)

    {

        var wordsMap = new Dictionary<string, int>();

        foreach(var word in words)

        {

            if (!wordsMap.ContainsKey(word))

            {

                wordsMap[word] = 0;

            }

            ++wordsMap[word];

        }

        return wordsMap;

    }

Complexity: O(n - k * k) where n is length of s, and k is LENGTH(words) * LENGTH(words[0]

[Uber][LeetCode] Asteroid Collision

Problem: We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Approach: We can use stack here to solve the problem easily. Here are the steps which we need to take:

Push the current number in stack if stack is empty or current number is positive or number at the top of the stack is negative. (No collision)

In case of current number is negative:

1. Pop from stack until stack is empty and top of the stack is positive and current number's absolute value is more than the top of the stack. (Resolve all the collisions)
2. If stack is empty or top of the stack is negative then push the current number. (All the collisions are resolved, we can safely put the current number)
3. Else if top of the stack is equal to absolute value of current number than perform a pop.(In case of equal size, asteroids explode each other)

That's all!

Implementation in C#:

    public int[] AsteroidCollision(int[] asteroids)

{

int length = asteroids?.Length ?? 0;

if (length == 0)

{

return new int[]{};

}

Stack<int> stack = new Stack<int>();

foreach (int size in asteroids)

{

if (size >= 0 || stack.Count == 0 || stack.Peek() < 0)

{

stack.Push(size);

}

else

{

int prev = stack.Peek();

while (stack.Count > 0 &&

stack.Peek() > 0 &&

stack.Peek() < -size)

{

prev = stack.Pop();

}

if (stack.Count == 0 || stack.Peek() < 0)

{

stack.Push(size);

}

else if (stack.Peek() == -size)

{

stack.Pop();

}

}

}

int[] answer = new int[stack.Count];

int i = stack.Count - 1;

while (stack.Count > 0)

{

answer[i--] = stack.Pop();

}

return answer;

}

Complexity: O(n)

[Uber][LeetCode] Find K Pairs with Smallest Sums

Problem: You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

Example:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]

Approach: The problem is straight forward. We can use Priority Queue / Heap to solve this problem.

Implementation in C#:

    public IList<IList<int>> KSmallestPairs(int[] nums1,

int[] nums2,

int k)

{

int length1 = nums1?.Length ?? 0;

int length2 = nums2?.Length ?? 0;

List<IList<int>> result = new List<IList<int>>();

if (length1 == 0 || length2 == 0)

{

return result;

}

PriorityQueue<int[], int> pq = new PriorityQueue<int[], int>();

for (int i = 0; i < length1 && i < k; ++i)

{

pq.Enqueue(new int[] {i, 0}, nums1[i] + nums2[0]);

}

while (pq.Count > 0 && result.Count < k)

{

int[] indices = pq.Dequeue();

result.Add(new List<int> {nums1[indices[0]],

                nums2[indices[1]]});

int index2 = indices[1] + 1;

if (index2 < length2)

{

pq.Enqueue(new int[] {indices[0], index2},

nums1[indices[0]] + nums2[index2]);

}

}

return result;

}

Complexity: klogk

[Uber][LeetCode]Random Pick with Weight

Problem: You are given a 0-indexed array of positive integers w where w[i] describes the weight of the ith index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).

Example:

Input
["Solution","pickIndex"]
[[[1]],[]]
Output
[null,0]

Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

Approach: One way to solve the problem is to create the array of length equals to the sum of all the numbers in the array w. Now put every index 'i' in this new array w[i] times and then just pick the index randomly in this new array and return the index. Let's take the above example [1, 3], the new array will be:

newArr = [0, 1, 1, 1]

So you can see now the if we can just pick an index randomly say 'randomIndex' and return the newArr[randomIndex], we have solved the problem and with good time complexity. The problem with this solution is the memory. Sum of all the numbers could be very large and taking an array of this size can be a problem so what we can do next?

We can use prefix sum. We can have a prefix sum array but with this we can't return a random index in constant time, instead we can use binary search to get the target in the prefix sum array. For above example our prefix sum array will be:

prefixSumArr = [1, 4]

Now we can generate a random number in between 1 to 4 and try to get its most suitable index in this sorted array using binary search. That's all!

Implementation in C#:

public class Solution

{

public Solution(int[] w)

    {

this.arr = new int[w.Length];

this.arr[0] = w[0];

for (int i = 1; i < w.Length; ++i)

{

this.arr[i] = this.arr[i - 1] + w[i];

}

this.rnd = new Random();

}

public int PickIndex()

    {

int target = rnd.Next(this.arr[this.arr.Length - 1]) + 1;

int low = 0, high = this.arr.Length - 1;

while (low < high)

{

int mid = low + (high - low) / 2;

if (arr[mid] == target)

{

return mid;

}

if (arr[mid] > target)

{

high = mid;

}

else

{

low = mid + 1;

}

}

return low;

}

Random rnd;

private int sum;

private int[] arr;

}

/**

* Your Solution object will be instantiated and called as such:

* Solution obj = new Solution(w);

* int param_1 = obj.PickIndex();

*/

Complexity: O(n) for construtor and O(logn) for pickIndex

[Uber][LeetCode] House Robber III

Problem: The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example:

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

Approach: We can use post order traversal here. At every node the maximum money can be one of the following:

1. Including node : Money at node + Max money without including direct left node + Max money without including direct right node
2. Without including node: Max money with/ without including left node + Max money with or with out including direct right node

That's all!

Implementation in C#:

    public int Rob(TreeNode root)

    {

int[] sums = this.RobHelper(root);

return Math.Max(sums[0], sums[1]);

}

private int[] RobHelper(TreeNode node)

{

if (node != null)

{

int[] leftSum = this.RobHelper(node.left);

int[] rightSum = this.RobHelper(node.right);

int sumIncludingNode = leftSum[1] + rightSum[1] + node.val;

int sumDiscludingNode = Math.Max(leftSum[0], leftSum[1]) +

                Math.Max(rightSum[0], rightSum[1]);

return new int[] { sumIncludingNode, sumDiscludingNode };

}

return new int[2];

}

Complexity: O(n)

[Uber][LeetCode] Course Schedule

Problem: There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

Approach: Basically it's a simple problem of finding a cycle in the Graph which can be achieved by DFS. 

Implementation in C#:

public class GraphNode

{

    public int Value { get; set; }

    public List<GraphNode> Neighbours { get; set; }

    public GraphNode(int val, List<GraphNode> neighbours = null)

    {

        this.Value = val;

        this.Neighbours = neighbours == null ? new List<GraphNode>() : neighbours;

    }

}

public class Graph

{

    public Graph()

    {

        this.nodes = new List<GraphNode>();

        this.nodesMap = new Dictionary<int, GraphNode>();

    }

    

    public void CreateNode(int value)

    {

        var node = new GraphNode(value);

        this.nodes.Add(node);

        this.nodesMap[value] = node;

    }

    

    public void AddNeighbour(int src, int neighbour)

    {

        var srcNode = this.nodesMap[src];

        var neighbourNode = this.nodesMap[neighbour];

        srcNode.Neighbours.Add(neighbourNode);

    }

    

    public bool DoesExistACycle()

    {

        if (this.nodes == null || this.nodes.Count <= 1)

        {

            return false;

        }        

        HashSet<int> visited = new HashSet<int>();

        foreach (var node in this.nodes)

        {

            if (!visited.Contains(node.Value))

            {

                HashSet<int> onCycle = new HashSet<int>();

                if (this.DFSCycle(node, onCycle, visited))

                {

                    return true;

                }

            }

        }

        return false;

    }

    

    private bool DFSCycle (GraphNode node, HashSet<int> onCycle, HashSet<int> visited)

    {

        if (visited.Contains(node.Value))

        {

            return false;

        }

        visited.Add(node.Value);

        onCycle.Add(node.Value);

        foreach (var neighbour in node.Neighbours)

        {

            if (onCycle.Contains(neighbour.Value) || this.DFSCycle(neighbour, onCycle, visited))

            {

                return true;

            }

        }

        onCycle.Remove(node.Value);

        return false;

    }

    

    private List<GraphNode> nodes;

    private Dictionary<int, GraphNode> nodesMap;

}

public class Solution 

{

    public bool CanFinish(int numCourses, int[][] prerequisites) 

    {

        var graph = new Graph();

        this.BuildGraphNodes(graph, numCourses);

        this.AddNeighbours(graph, prerequisites);

        return !graph.DoesExistACycle();

    }

    

    private void BuildGraphNodes(Graph graph, int numCourses)

    {

        for (int i = 0; i < numCourses; ++i)

        {

            graph.CreateNode(i);

        }

    }

    

    private void AddNeighbours(Graph graph, int[][] prerequisites)

    {

        foreach (var prerequisite in prerequisites)

        {

            graph.AddNeighbour(prerequisite[1], prerequisite[0]);

        }

    }

}

Complexity: O(n)

[Uber][LeetCode] Employee Importance

Problem: You have a data structure of employee information, including the employee's unique ID, importance value, and direct subordinates' IDs.

You are given an array of employees employees where:

• employees[i].id is the ID of the ith employee.
• employees[i].importance is the importance value of the ith employee.
• employees[i].subordinates is a list of the IDs of the direct subordinates of the ith employee.

Given an integer id that represents an employee's ID, return the total importance value of this employee and all their direct and indirect subordinates.

Example:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

Input: employees = [[1,2,[5]],[5,-3,[]]], id = 5
Output: -3
Explanation: Employee 5 has an importance value of -3 and has no direct subordinates.
Thus, the total importance value of employee 5 is -3.

Constraints:

• 1 <= employees.length <= 2000
• 1 <= employees[i].id <= 2000
• All employees[i].id are unique.
• -100 <= employees[i].importance <= 100
• One employee has at most one direct leader and may have several subordinates.
• The IDs in employees[i].subordinates are valid IDs.

Approach: If we look closely it is kind of a tree problem. We are given the node of the tree and we need to get the sum of all the values of the nodes of the subtree whose root is given input node. 

We can build a tree using the given info and then we can simply apply DFS / preorder traversal to get the sum of the importance of all the nodes of the subtree.

Implementation in C#:

/*

// Definition for Employee.

class Employee {

    public int id;

    public int importance;

    public IList<int> subordinates;

}

*/

public class EmployeeValue

{

    public int Importance { get; set; }

    public IList<int> Children { get; set; }

    

    public EmployeeValue(int importance, IList<int> children)

    {

        this.Importance = importance;

        this.Children = children;

    }

}

class Solution 

{

    public int GetImportance(IList<Employee> employees, int id) 

    {

        var employeeTree = this.BuildEmployeeTree(employees);

        return this.GetImportanceHelper(employeeTree, id);

    }

    

    private int GetImportanceHelper(Dictionary<int, EmployeeValue> employeeTree, int currId)

    {

        int totalImportance = employeeTree[currId].Importance;

        foreach (int id in employeeTree[currId].Children)

        {

            totalImportance += this.GetImportanceHelper(employeeTree, id);

        }

        return totalImportance;

    }

    

    private Dictionary<int, EmployeeValue> BuildEmployeeTree(IList<Employee> employees)

    {

        var tree = new Dictionary<int, EmployeeValue>();

        foreach(var employee in employees)

        {

            tree[employee.id] = new EmployeeValue(employee.importance, employee.subordinates);

        }

        return tree;

    }

}

Complexity: O(n) where n is the length of the employees list.

[Uber][LeetCode] Reverse Pairs

Problem: Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where:

• 0 <= i < j < nums.length and
• nums[i] > 2 * nums[j].

Example:

Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1

Approach: We can use Merge sort approach here. The only change which we need to make is while merging the two (left and right) sorted array we can check how many reverse pair are there.

 

Implementation in C#:

    public int ReversePairs(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        return this.CountReversePairs(nums, 0, length - 1);

    }

    private int CountReversePairs(int[] nums, int left, int right)

    {

        if (left >= right)

        {

            return 0;

        }

        int mid = left + (right - left) / 2;

        int leftRevCount = this.CountReversePairs(nums, left, mid);

        int rightRevCount = this.CountReversePairs(nums, mid + 1, right);

        int mergeRevCount = this.Merge(nums, left, mid, right);

        return leftRevCount + rightRevCount + mergeRevCount;

    }

    private int Merge(int[] nums, int left, int mid, int right)

    {

        int i = left;

        int j = mid + 1;

        var temp = new List<int>();

        int revPairsCount = this.GetReversPairs(nums, left, mid, right);

        while (i <= mid && j <= right)

        {

            if (nums[i] > nums[j])

            {

                temp.Add(nums[j++]);

            }

            else

            {

                temp.Add(nums[i++]);

            }

        }

        while (i <= mid)

        {

            temp.Add(nums[i++]);

        }

        while (j <= right)

        {

            temp.Add(nums[j++]);

        }

        i = left;

        for (j = 0; j < temp.Count; ++j)

        {

            nums[i++] = temp[j];

        }

        return revPairsCount;

    }

    private int GetReversPairs(int[] nums, int left, int mid, int right)

    {

        int j = mid + 1;

        int revPairsCount = 0;

        for (int i = left; i <= mid; ++i)

        {

            while (j <= right && nums[i] > (long)(2 * (long)nums[j]))

            {

                ++j;

            }

            revPairsCount += (j - (mid + 1));

        }

        return revPairsCount;

    }

Complexity: O(nlogn)

[Uber][LeetCode] Flatten Nested List Iterator

Problem: You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList

res = []

while iterator.hasNext()

    append iterator.next() to the end of res

return res

If res matches the expected flattened list, then your code will be judged as correct.

Example:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Approach: We will flatten the list using DFS in an additional DS like Queue and then just return it from that Queue when HasNext or Next is called.

Implementation in C#:

/**

 * // This is the interface that allows for creating nested lists.

 * // You should not implement it, or speculate about its implementation

 * interface NestedInteger {

 *

 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.

 *     bool IsInteger();

 *

 *     // @return the single integer that this NestedInteger holds, if it holds a single integer

 *     // Return null if this NestedInteger holds a nested list

 *     int GetInteger();

 *

 *     // @return the nested list that this NestedInteger holds, if it holds a nested list

 *     // Return null if this NestedInteger holds a single integer

 *     IList<NestedInteger> GetList();

 * }

 */

public class NestedIterator 

{

    public NestedIterator(IList<NestedInteger> nestedList) {

        this.queue = new Queue<int>();

        foreach (NestedInteger integer in nestedList)

        {

            this.FillQueue(integer);

        }

    }

    public bool HasNext() 

    {

        return queue.Count > 0;

    }

    public int Next() 

    {

        return this.HasNext() ? queue.Dequeue() : -1;

    }

    

    private void FillQueue(NestedInteger nestedInteger)

    {

        if (nestedInteger.IsInteger())

        {

            this.queue.Enqueue(nestedInteger.GetInteger());

        }

        else

        {

            IList<NestedInteger> list = nestedInteger.GetList();

            foreach (NestedInteger integer in list)

            {

                this.FillQueue(integer);

            }

        }

    }

    

    private Queue<int> queue; 

}

Complexity: O(n)