Buttercola: April 2018

Sunday, April 29, 2018

Leetcode 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Code (Java):

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ans = new int[2];
         
        if (nums == null || nums.length < 2) {
            return ans;
        }
         
        Map<Integer, Integer> map = new HashMap<>();
         
        for (int i = 0; i < nums.length; i++) {
            int comp = target - nums[i];
             
            if (map.containsKey(comp)) {
                ans[0] = map.get(comp);
                ans[1] = i;
                break;
            } else {
                map.put(nums[i], i);
            }
        }
         
        return ans;
    }
}

Tuesday, April 24, 2018

Leetcode 809. Expressive Words

Sometimes people repeat letters to represent extra feeling, such as "hello" -> "heeellooo", "hi" -> "hiiii". Here, we have groups, of adjacent letters that are all the same character, and adjacent characters to the group are different. A group is extended if that group is length 3 or more, so "e" and "o" would be extended in the first example, and "i" would be extended in the second example. As another example, the groups of "abbcccaaaa" would be "a", "bb", "ccc", and "aaaa"; and "ccc" and "aaaa" are the extended groups of that string.

For some given string S, a query word is stretchy if it can be made to be equal to S by extending some groups. Formally, we are allowed to repeatedly choose a group (as defined above) of characters c, and add some number of the same character c to it so that the length of the group is 3 or more. Note that we cannot extend a group of size one like "h" to a group of size two like "hh" - all extensions must leave the group extended - ie., at least 3 characters long.

Given a list of query words, return the number of words that are stretchy.

Example:
Input: 
S = "heeellooo"
words = ["hello", "hi", "helo"]
Output: 1
Explanation: 
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not extended.

Notes:

0 <= len(S) <= 100.
0 <= len(words) <= 100.
0 <= len(words[i]) <= 100.
S and all words in words consist only of lowercase letters

Analysis:

The problem asks for a word in a list of words, it's stretchy if we can extend any character to the corresponding one in the S by repeating three or more times.

Code (Java):

class Solution {
    public int expressiveWords(String S, String[] words) {
        int ans = 0;
        for (String word : words) {
            if (isStretchy(S, word)) {
                ans++;
            }
        }
         
        return ans;
    }
     
    private boolean isStretchy(String s, String word) {
        int i = 0;
        int j = 0;
        int m = s.length();
        int n = word.length();
         
        while (i < m && j < n) {
            // Step 1: move j to the next group
            //
            while (i < m && j < n && s.charAt(i) == word.charAt(j)) {
                i++;
                j++;
            }
             
            // Step 2: move i to the next group
            //
            while (i > 0 && i < m && s.charAt(i) == s.charAt(i - 1)) {
                i++;
            }
             
            // Step 3: check if it's not stretchy
            //
            if (i < 3 || s.charAt(i - 1) != s.charAt(i - 2) || s.charAt(i - 2) != s.charAt(i - 3)) {
                break;
            }
        }
         
        return i == m && j == n;
    }
}

A better solution:
If we can pre-process the list of words and "cache" something, it will make the compare faster.

Monday, April 23, 2018

Leetcode 816. Ambiguous Coordinates

We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)". Then, we removed all commas, decimal points, and spaces, and ended up with the string S. Return a list of strings representing all possibilities for what our original coordinates could have been.

Our original representation never had extraneous zeroes, so we never started with numbers like "00", "0.0", "0.00", "1.0", "001", "00.01", or any other number that can be represented with less digits. Also, a decimal point within a number never occurs without at least one digit occuring before it, so we never started with numbers like ".1".

The final answer list can be returned in any order. Also note that all coordinates in the final answer have exactly one space between them (occurring after the comma.)

Example 1:
Input: "(123)"
Output: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

Example 2:
Input: "(00011)"
Output:  ["(0.001, 1)", "(0, 0.011)"]
Explanation: 
0.0, 00, 0001 or 00.01 are not allowed.

Example 3:
Input: "(0123)"
Output: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

Example 4:
Input: "(100)"
Output: [(10, 0)]
Explanation: 
1.0 is not allowed.

Note:

4 <= S.length <= 12.
S[0] = "(", S[S.length - 1] = ")", and the other elements in S are digits.

Code (Java):

class Solution {
    public List<String> ambiguousCoordinates(String S) {
        List<String> ans = new ArrayList<>();
         
        // step 1: split the string S into two halves, by inserting a comma
        //
        for (int i = 2; i <= S.length() - 2; i++) {
            List<String> leftCoordinates = findAllValidCoordinates(S.substring(1, i));
            List<String> rightCoordinates = findAllValidCoordinates(S.substring(i, S.length() - 1));
             
            for (String left : leftCoordinates) {
                for (String right : rightCoordinates) {
                    String s = '(' + left + ", " + right + ')';
                    ans.add(s);
                }
            }
        }
         
        return ans;
    }
     
    private List<String> findAllValidCoordinates(String s) {
        List<String> ans = new ArrayList<>();
         
        for (int i = 1; i <= s.length(); i++) {
            String left = s.substring(0, i);
            String right = s.substring(i, s.length());
             
            if ((left.equals("0") || !left.startsWith("0")) && !right.endsWith("0")) {
                String validString = i == s.length() ? left : left + '.' + right;
                ans.add(validString);
            }
        }
         
        return ans;
    }
}

Sunday, April 22, 2018

Leetcode 817. Linked List Components

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:

Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Note:

If N is the length of the linked list given by head, 1 <= N <= 10000.
The value of each node in the linked list will be in the range [0, N - 1].
1 <= G.length <= 10000.
G is a subset of all values in the linked list.

Analysis:

Scanning through the list, if node.val is in G and node.next.val isn't (including if node.next is null), then this must be the end of a connected component.

Code (Java):

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int numComponents(ListNode head, int[] G) {
        Set<Integer> setG = new HashSet<>();
         
        // insert each number in G into the hash set
        //
        for (int num : G) {
            setG.add(num);
        }
         
        int numCC = 0;
         
        // Iterate all nodes in the linked list and get number of cc
        //
        while (head != null) {
            if (setG.contains(head.val) && 
                (head.next == null || !setG.contains(head.next.val))) {
                numCC++;
            }
             
            head = head.next;
        }
         
        return numCC;
     }
}

Leetcode 807. Max Increase to Keep City Skyline

In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.

At the end, the "skyline" when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city's skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.

What is the maximum total sum that the height of the buildings can be increased?

Example:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation: 
The grid is:
[ [3, 0, 8, 4], 
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0] ]

The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

Notes:

1 < grid.length = grid[0].length <= 50.
All heights grid[i][j] are in the range [0, 100].
All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j] rectangular prism.

Code (Java):

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int num = grid.length;
         
        int ans = 0;
         
        int[] skylineTopBottom = new int[num];
        int[] skylineLeftRight = new int[num];
         
        // Step 1, get skyline from top and bottom, and from left and right
        //
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                skylineTopBottom[j] = Math.max(skylineTopBottom[j], grid[i][j]);
                skylineLeftRight[i] = Math.max(skylineLeftRight[i], grid[i][j]);
            }
        }
         
        // Step 2: scan the grid again and calculate the max height we can increase
        //
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                ans += Math.min(skylineTopBottom[j], skylineLeftRight[i]) - grid[i][j];
            }
        }
         
        return ans;
    }
}

Leetcode 788. Rotated Digits

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid.

Now given a positive number N, how many numbers X from 1 to N are good?

Example:
Input: 10
Output: 4
Explanation: 
There are four good numbers in the range [1, 10] : 2, 5, 6, 9.
Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Note:

N will be in range [1, 10000].

Solution:

Brute-force. Check each number from 1 to N and see if it's a good number.

Code (Java):

class Solution {
    public int rotatedDigits(int N) {
        int count = 0;
         
        for (int num = 1; num <= N; num++) {
            if (isGoodNumber(num)) {
                count++;
            }
        }
         
        return count;
    }
     
    private boolean isGoodNumber(int num) {
        boolean has2569 = false;
        while (num > 0) {
            int digit = num % 10;
            has2569 |= contains2569(digit);
             
            if (contains347(digit)) {
                return false;
            }
            num /= 10;
        }
         
        return has2569;
    }
     
    private boolean contains347(int digit) {
        if (digit == 3 || digit == 4 || digit == 7) {
            return true;
        }
         
        return false;
    }
     
    private boolean contains2569(int digit) {
        if (digit == 2 || digit == 5 || digit == 6 || digit == 9) {
            return true;
        }
         
        return false;
    }
}

Saturday, April 21, 2018

Leetcode 791. Custom Sort String

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

Example :
Input: 
S = "cba"
T = "abcd"
Output: "cbad"
Explanation: 
"a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a". 
Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.

Note:

S has length at most 26, and no character is repeated in S.
T has length at most 200.
S and T consist of lowercase letters only.

Analysis:

The problem is simply a merge sort.

Code (Java):

class Solution {
    public String customSortString(String S, String T) {
        int[] dict = new int[26];
         
        for (int i = 0; i < dict.length; i++) {
            dict[i] = Integer.MAX_VALUE;
        }
         
        // Step 1: note the position of each char in S
        //
        for (int i = 0; i < S.length(); i++) {
            dict[S.charAt(i) - 'a'] = i;
        }
         
        // Step 2: merge sort
        //
        char[] Aux = new char[T.length()];
        char[] A = T.toCharArray();
        customMergeSort(dict, A, Aux, 0, A.length - 1);
         
        return String.copyValueOf(A);
    }
     
    private void customMergeSort(int[] dict, char[] A, char[] Aux, int lo, int hi) {
         
        if (lo >= hi) {
            return;
        }
         
        int mid = lo + (hi - lo) / 2;
         
        customMergeSort(dict, A, Aux, lo, mid);
        customMergeSort(dict, A, Aux, mid + 1, hi);
         
        customMerge(dict, A, Aux, lo, mid, hi);
    }
     
    private void customMerge(int[] dict, char[] A, char[] Aux, int lo, int mid, int hi) {
        for (int i = lo; i <= hi; i++) {
            Aux[i] = A[i];
        }
         
        int i = lo;
        int j = mid + 1;
         
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                A[k] = Aux[j++];
            } else if (j > hi) {
                A[k] = Aux[i++];
            } else if (dict[Aux[i] - 'a'] < dict[Aux[j] - 'a']) {
                A[k] = Aux[i++];;
            } else if (dict[Aux[i] - 'a'] >= dict[Aux[j] - 'a']) {
                A[k] = Aux[j++];
            }
        }
    }
}

A linear time solution:

class Solution {
    public String customSortString(String S, String T) {
        // Step 1: count the freq of each char in T
        //
        int[] freq = new int[26];
         
        for (int i = 0; i < T.length(); i++) {
            char c = T.charAt(i);
            freq[c - 'a']++;
        }
         
        // step 2: scan the string S and print the number of chars in T
        //
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
             
            while (freq[c - 'a'] > 0) {
                sb.append(c);
                freq[c - 'a']--;
            }
        }
         
        // step 3: scan the freq again and append anything not zero
        //
        for (int i = 0; i < freq.length; i++) {
            while (freq[i] > 0) {
                sb.append((char) (i + 'a'));
                freq[i]--;
            }
        }
         
        return sb.toString();
    }
}

Friday, April 20, 2018

Leetcode 794. Valid Tic-Tac-Toe State

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The " " character represents an empty square.

Here are the rules of Tic-Tac-Toe:

Players take turns placing characters into empty squares (" ").
The first player always places "X" characters, while the second player always places "O" characters.
"X" and "O" characters are always placed into empty squares, never filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.

Example 1:
Input: board = ["O  ", "   ", "   "]
Output: false
Explanation: The first player always plays "X".

Example 2:
Input: board = ["XOX", " X ", "   "]
Output: false
Explanation: Players take turns making moves.

Example 3:
Input: board = ["XXX", "   ", "OOO"]
Output: false

Example 4:
Input: board = ["XOX", "O O", "XOX"]
Output: true

Note:

board is a length-3 array of strings, where each string board[i] has length 3.
Each board[i][j] is a character in the set {" ", "X", "O"}

Analysis:

The problem only asks if the given board is valid. A board is valid only if

1. number of X - number of O == 0

2. number of X - number of O == 1

If the number of X is equal to number of O, we need to check player X does not win. Otherwise, player O must be less than player X.

If the number of X - number of O = 1, we need to check player O does not win. Otherwise, the game has stopped and player X cannot be greater than player O.

Code (Java):

class Solution {
    public boolean validTicTacToe(String[] board) {
        char[][] gameBoard = new char[3][3];
         
        for (int i = 0; i < 3; i++) {
            gameBoard[i] = board[i].toCharArray();
        }
         
        // Get number of X player and O player
        //
        int numOfX = 0;
        int numOfO = 0;
         
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                char c = gameBoard[i][j];
                 
                if (c == 'X') {
                    numOfX++;
                } else if (c == 'O') {
                    numOfO++;
                }
            }
        }
         
        if (numOfX < numOfO || numOfX - numOfO > 1) {
            return false;
        }
         
        if (numOfX - numOfO == 1) {
            if (hasWon(gameBoard, 'O')) {
                return false;
            }
        }
         
        if (numOfX == numOfO) {
            if (hasWon(gameBoard, 'X')) {
                return false;
            }
        }
         
        return true;
    }
     
    private boolean hasWon(char[][] gameBoard, char player) {
        for (int i = 0; i < 3; i++) {
            if (gameBoard[i][0] == player && 
                gameBoard[i][1] == gameBoard[i][0] && 
                gameBoard[i][2] == gameBoard[i][1]) {
                return true;
            }
             
            if (gameBoard[0][i] == player && 
                gameBoard[1][i] == gameBoard[0][i] && 
                gameBoard[2][i] == gameBoard[1][i]) {
                return true;
            }
             
            if (player == gameBoard[0][0] && 
                gameBoard[0][0] == gameBoard[1][1] && 
                gameBoard[1][1] == gameBoard[2][2]) {
                return true;
            }
             
            if (player == gameBoard[0][2] && 
                gameBoard[1][1] == gameBoard[0][2] && 
                gameBoard[1][1] == gameBoard[2][0]) {
                return true;
            }
        }
         
        return false;
    }
}

Thursday, April 19, 2018

Leetcode 792. Number of Matching Subsequences

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Example :
Input: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
Output: 3
Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace".

Note:

All words in words and S will only consists of lowercase letters.
The length of S will be in the range of [1, 50000].
The length of words will be in the range of [1, 5000].
The length of words[i] will be in the range of [1, 50]

Brute Force Solution:

The most straight forward solution would be for each word in the words[], check with S and see if it's the subsequence of S.

Code (Java):

class Solution {
    public int numMatchingSubseq(String S, String[] words) {
        int ans = 0;
         
        for (String word : words) {
            if (isSubsequence(S, word)) {
                ans++;
            }
        }
         
        return ans;
    }
     
    private boolean isSubsequence(String s, String w) {
        int sIndex = 0;
        int wIndex = 0;
         
        while (wIndex < w.length() && sIndex < s.length()) {
            if (s.charAt(sIndex) == w.charAt(wIndex)) {
                sIndex++;
                wIndex++;
            }
            else {
                sIndex++;
            }
        }
         
        return wIndex == w.length();
    }
}

Analysis:
The time complexity is O(S *(M + N)))
If we just compare two strings, the solution above is the best solution since we need to compare each character in the strings anyway.

For this problem, however, since the length of the words is very big, it would be better if we can memorize something we did in the past.

A better solution (DP):

Monday, April 16, 2018

Leetcode 797. All Paths From Source to Target

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, ..., graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:
Input: [[1,2], [3], [3], []] 
Output: [[0,1,3],[0,2,3]] 
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:

The number of nodes in the graph will be in the range [2, 15].
You can print different paths in any order, but you should keep the order of nodes inside one path.

Analysis:

A DFS for all the nodes should solve the problem.

Code (Java):

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> ans = new ArrayList<>();
         
        if (graph == null || graph.length == 0) {
            return ans;
        }
         
        // DFS
        //
        List<Integer> path = new ArrayList<>();
        findPathToTarget(graph, 0, path, ans);
         
        return ans;
    }
     
    private void findPathToTarget(int[][] graph, int source, List<Integer> path,

                                  List<List<Integer>> ans) {
        path.add(source);
         
        if (source == graph.length - 1) {
            List<Integer> cloneList = new ArrayList<>(path);
            ans.add(cloneList);
        }
         
        for (int neighbor : graph[source]) {
            findPathToTarget(graph, neighbor, path, ans);
        }
         
        path.remove(path.size() - 1);
    }
}

Complexity Analysis

Time Complexity: $O(2^N N^2)$ . We can have exponentially many paths, and for each such path, our prepending operation path.add(0, node) will be $O(N^2)$ .
Space Complexity: $O(2^N N)$ , the size of the output dominating the final space complexity.

Sunday, April 15, 2018

Leetcode 802. Find Eventual Safe States

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.

Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.

Which nodes are eventually safe? Return them as an array in sorted order.

The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph. The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.

Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.

Note:

graph will have length at most 10000.
The number of edges in the graph will not exceed 32000.
Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

Solution:

The problem is actually asking if we can find a cycle in a graph. If yes, then all the nodes in the cycle are unstable. We can use DFS to find out a cycle in a graph. NOTE that we may do some pruning optimization.

Code (Java): -- TLE error

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> ans = new ArrayList<>();
         
        if (graph == null || graph.length == 0) {
            return ans;
        }
         
        int numOfNodes = graph.length;
         
        boolean[] stableNodes = new boolean[numOfNodes];
        // Init as true
        //
        for (int i = 0; i < numOfNodes; i++) {
            stableNodes[i] = true;
        }
         
        // DFS for each node and find cycle in a graph
        //
        for (int i = 0; i < numOfNodes; i++) {
            // Pruning. If the node is blacklisted, skip and go to next node
            //
            if (stableNodes[i] == false) {
                continue;
            }
             
            findCycleInGraph(graph, i, stableNodes);
        }
         
        // stableNodes is in sorted order
        //
        for (int i = 0; i < numOfNodes; i++) {
            if (stableNodes[i]) {
                ans.add(i);
            }
        }
         
        return ans;
    }
     
    private void findCycleInGraph(int[][] graph, int source, boolean[] stableNodes) {
        Set<Integer> visitedNodes = new HashSet<>();
         
        findCycleInGraphHelper(graph, source, stableNodes, visitedNodes);
    }
     
    private boolean findCycleInGraphHelper(int[][] graph, int source, boolean[] stableNodes, Set<Integer> visitedNodes) {
        // Check the cycle in the graph
        //
        if (visitedNodes.contains(source)) {
            addToBlackList(visitedNodes, stableNodes);
            return true;
        }
         
        // Add source node into the visited list
        //
        visitedNodes.add(source);
         
        // DFS the graph
        //
        boolean hasCycle = false;
         
        for (int neighbor : graph[source]) {
            hasCycle = findCycleInGraphHelper(graph, neighbor, stableNodes, visitedNodes);
            // pruning
            //
            if (hasCycle) {
                break;
            }
        }
         
        // Remove the node from the visited list
        //
        visitedNodes.remove(source);
         
        return hasCycle;
    }
     
    private void addToBlackList(Set<Integer> visitedNodes, boolean[] stableNodes) {
        Iterator it = visitedNodes.iterator();
         
        while (it.hasNext()) {
            int visitedNode = (int)it.next();
            stableNodes[visitedNode] = false;
        }
    }
}

A Slightly optimized solution:
In the previous solution, if we can find a cycle in a graph, then all the nodes in the cycle are unstable. So we don't need to traverse from that node again. Another optimization could be, if we cannot find a cycle after traversing all the paths, we can mark this node as stable. Then we don't need to check it again.

To implement this, we can use a black-white node. A node is black means the node is unstable, while the node is white means it's stable.

Code (Java):

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> ans = new ArrayList<>();
         
        if (graph == null || graph.length == 0) {
            return ans;
        }
         
        int numOfNodes = graph.length;
         
        // 2 is stable, 1 is unstable
        //
        int[] color = new int[numOfNodes];
         
        for (int i = 0; i < numOfNodes; i++) {
            // IF the color is 1 or 2, then skip
            //
            if (color[i] == 1 || color[i] == 2) {
                continue;
            }
             
            findCycleInGraph(graph, i, color);
        }
         
        // Construct result
        //
        for (int i = 0; i < numOfNodes; i++) {
            if (color[i] == 2) {
                ans.add(i);
            }
        }
         
        return ans;
    }
     
    private boolean findCycleInGraph(int[][] graph, int source, int[] color) {
        if (color[source] == 2) {
            return false;
        }
         
        if (color[source] == 1) {
           return true; 
        }
         
        color[source] = 1;
         
        for (int neighbor : graph[source]) {
            boolean hasCycle = findCycleInGraph(graph, neighbor, color);
             
            if (hasCycle) {
                return true;
            }
        }
         
        color[source] = 2;
         
        return false;
    }
}

Complexity Analysis

Time Complexity: $O(N + E)$ , where $N$ is the number of nodes in the given graph, and $E$ is the total number of edges.
Space Complexity: $O(N)$ in additional space complexity.