Day 10 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#457. Circular Array Loop(Medium/JavaScript)

Intro: I am a former accountant turned software engineer graduated from coding bootcamp in January 2022. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:

• Pick a leetcode problem randomly or Online Assessment from targeted companies.
• Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
• Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
• Code out the solution in LeetCode without looking at the solutions
• Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.

---

457. Circular Array Loop

Difficulty: Medium Language: JavaScript

You are playing a game involving a circular array of non-zero integers nums. Each nums[i] denotes the number of indices forward/backward you must move if you are located at index i:

• If nums[i] is positive, move nums[i] steps forward, and
• If nums[i] is negative, move nums[i] steps backward.

Since the array is circular, you may assume that moving forward from the last element puts you on the first element, and moving backwards from the first element puts you on the last element.

A cycle in the array consists of a sequence of indices seq of length k where:

• Following the movement rules above results in the repeating index sequence seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...
• Every nums[seq[j]] is either all positive or all negative.
• k > 1

Return true if there is a cycle in nums, or false otherwise.

Example 1:

Input: nums = [2,-1,1,2,2]
Output: true
Explanation:
There is a cycle from index 0 -> 2 -> 3 -> 0 -> ...
The cycle's length is 3.

Example 2:

Input: nums = [-1,2]
Output: false
Explanation:
The sequence from index 1 -> 1 -> 1 -> ... is not a cycle because
the sequence's length is 1.
By definition the sequence's length must be strictly greater than
1 to be a cycle.

Example 3:

Input: nums = [-2,1,-1,-2,-2]
Output: false
Explanation:
The sequence from index 1 -> 2 -> 1 -> ... is not a cycle because
nums[1] is positive, but nums[2] is negative.
Every nums[seq[j]] must be either all positive or all negative.

Constraints:

• 1 <= nums.length <= 5000
• -1000 <= nums[i] <= 1000
• nums[i] != 0

---

Solution:

var circularArrayLoop = function(nums) {

    for(let i = 0 ; i < nums.length ; i++){

//Loop (note 1) throught array 'nums'.This array maybe has more
//than one cycle that we don't know, so we need to run each
//element to check cycle. 

        let ans = [];

//create an empty array to store the index

        let dir = Math.sign(nums[i]);

//use 'dir' (note 2) to check they all positive or negative

        let j = i;

        while(nums[j] != 0 && Math.sign(nums[j]) == dir){

//while (note 3) num[j] is not 0 and it's the same direction as
//nums[i]. 

            let preJ = j;

//set a temp variable to store j

            j += nums[j];

//add the value of nums[j] to j and get an updated j. For example,
//if j is initially 1 and value of nums[j] is '2', then updated
//index j will be 3 

            j %= nums.length;

//calculate the remainder of j % nums.length (note 5)

            j += j < 0 ? nums.length : 0;

            ans.push(preJ);

//save the index to answer array (note 6)

            nums[preJ] = 0;

//if this element has been checked, change it to zero.
//if the nums[j]  == 0 , means we find this cycle and get the
//start point called j.

        }
        let pos = ans.indexOf(j);

//find j in answer array (note 7), if found then there is a cycle

        if(ans.length > 1 && pos != -1 && pos != ans.length - 1) 

//if answer array exist, j can be found in the answer array and
//the sequence's length is more than 1, return true

 return true;

    }

    return false;
};

Solution Submission detail as of 2/21/2022
(Data below could vary since there are new tests/submissions daily)

• Runtime: 68ms
• Memory Usage: 42.1mb

---

References:
LeetCode Problem Link
LeetCode Discussion: tony11tony11t
Note 1: Loop and Iteration
Note 2: Math.sign()
Note 3: while statement
Note 4: Addition assignment
Note 5: Remainder assignment
Note 6: Array.push()
Note 7: Array.indexOf()
Blog Cover Image Credit