Leetcode 3

Question 1

Longest Common Prefix

Answer 1

Solution 1 (Vertical Scan): public String longestCommonPrefix(String[] strs) {
 if (strs == null || strs.length == 0) return "";
 for (int i = 0; i \< strs[0].length() ; i++){
 char c = strs[0].charAt(i);
 for (int j = 1; j \< strs.length; j ++) {
 if (i == strs[j].length() || strs[j].charAt(i) != c)
 return strs[0].substring(0, i); 
 }
 }
 return strs[0];
Time: O(S), S = m\*n with n equal strings of length m. Space: O(1)

Solution 2 (Sort): sort the input list of words, then just compare chars of first and last words. Time: O(m*nlogn) where m is the average length of each word (use StringBuilder)

Question 2

Maximum Subarray

Answer 2

DP: question is do we include each successive element in our max sub array or not? init dp[]. init dp[0] = A[0], int max = dp[0]. Loop through i to len of input array and set: dp[i] = Math.max(A[i] + dp[i - 1] , A[i]); max = Math.max(max, dp[i])
Time: O(n), space: O(n)

if (nums.length == 0) {

return 0;

}

int globalMax = 0;

int[] dp = new int[nums.length];

dp[0] = nums[0];

globalMax = dp[0];

int i = 1;

while (i < nums.length) {

dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);

globalMax = Math.max(globalMax, dp[i]);

i ++;

}

return globalMax;

Question 3

Move Zeroes (must be done in-place)

Answer 3

keep track of number of zeroes, if encounter a non-zero then swap that number with nums[i-number_of_zeroes]

int numZeroes = 0;
int i = 0;

while (i < nums.length) {
if (nums[i] == 0) {
numZeroes ++;
}
if (nums[i] != 0) {
int t = nums[i];
nums[i] = 0;
nums[i-numZeroes] = t;
}
i ++;
}

Question 4

Unique Number of Occurrences

Answer 4

count occurrences of each char; compare if numbers of distinct chars and distinct counts are equal

public boolean uniqueOccurrences(int[] arr) {
Map count = new HashMap<>();
for (int a : arr)
count.put(a, 1 + count.getOrDefault(a, 0));
return count.size() == new HashSet<>(count.values()).size();
}

Creating a HashSet with e.g. (1, 2, 2, 3) automatically removes duplicates, as a HashSet cannot have duplicate values.

Question 5

Number of Islands

Answer 5

DFS: Linear scan the grid. If a node contains a 1, it is a root node that triggers a DFS. During DFS, set every visited node to 0 to mark as visited. Count the number of root nodes that trigger DFS, this will be the number of islands. Base case = if grid == null or grid.length = 0

g = grid;

int c = 0;

y = g.length;
if (y == 0) return 0;
x = g[0].length;

for (int i = 0; i < y; i++) {
for (int j = 0; j < x; j++) {
if (g[i][j] == ‘1’) {
dfs(i, j);
c++;
}
}
}
return c;

private void dfs(int i, int j) {

 // Check for invalid indices and for sites that aren't land
 if (i \< 0 || i \>= y || j \< 0 || j \>= x || g[i][j] != '1') return;

 // Mark the site as visited
 g[i][j] = '0';

dfs(i + 1, j);
dfs(i - 1, j);
dfs(i, j + 1);
dfs(i, j - 1);

Time: O(M*N) b/c we look at each cell once
Space: worst case O(M*N) if matrix is all land, then DFS goes M*N deep
BFS has same time but space is O(min(M,N)). This is because of the “diagonal” representation of BFS in a grid

Question 6

Reverse Integer (123 -> 321)

Answer 6

“Pop” off each digit from front and “add” to the back

public int reverse(int x) {
int prevRev = 0 , rev= 0;
while( x != 0){
rev= rev*10 + x % 10;
if((rev - x % 10) / 10 != prevRev){
return 0;
}
prevRev = rev;
x= x/10;
}
return rev;
}

the “if” essentially undoes the prev operation and checkf if we overflowed or not.
time: O(log_10(x)), space: O(1)

Question 7

Accounts Merge Strategy

Answer 7

DFS: represent emails as nodes and an edge means two emails are connected and thus belong to the same person.

1) create adjacency list: for each account add an edge between first email and other emails
2) Traverse over accounts: for each account, check if first email was already visited. If so, then do not start a new DFS. Otherwise perform DFS with that email as source node
3) During each DFS, store traversed emails in an array and mark them as visited
4) After DFS, sort the emails and add accountName to the start of mergedAccount
5) Store mergedAccount in output list of mergedAccounts

Question 8

Accounts Merge Code (DFS)

Answer 8

Map> graph = new HashMap<>();
Map emailToName = new HashMap<>();

public void dfs(List result, Map> graph, Set visited, String curPoint) {
result.add(curPoint);
Set neighbors = graph.get(curPoint);
for (String neighbor : neighbors) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
dfs(result, graph, visited, neighbor);
}
}

Question 9

Accounts Merge Code (

Answer 9

// step 1: build graph that connects all emails have relationships
for (List account : accounts) {
String name = account.get(0);
for (int i = 1; i < account.size(); i++) {
graph.putIfAbsent(account.get(i), new HashSet<>());
emailToName.put(account.get(i), name);
if (i != 1) {
graph.get(account.get(i)).add(account.get(i - 1));
graph.get(account.get(i - 1)).add(account.get(i));
}
}
}

// step 2: DFS traversal to traverse all nodes in every single component and generate each result list individually
List> result = new ArrayList<>();
Set visited = new HashSet<>();
for (String email : graph.keySet()) {
if (!visited.contains(email)) {
visited.add(email);
List newList = new ArrayList<>();
dfs(newList, graph, visited, email);
Collections.sort(newList);
newList.add(0, emailToName.get(newList.get(0)));
result.add(newList);
}
}
return result;

Question 10

Accounts Merge Time/Space

Answer 10

Time: O(NKlogNK), N is number of accounts, K is max length of an account. Worst case, all emails belong to a single person, so total email = N*K and DFS will perform NK operations (we are sorting mergedAccounts)
Space: O(NK). Building adjacency list takes NK space. Call stack for DFS takes NK space in worst case. Collections.sort takes O(NK) space