Leetcode Weekly Contest 194 Swift solutions

From XOR to Krustal

Image for post
Image for post
Photo by Abigail Miller on Unsplash

This article is about the 4 challenges in the LeetCode Weekly Contest 194. That is:

  • 1486 XOR Operation in an Array
  • 1487 Making File Names Unique
  • 1488 Avoid Flood in The City
  • 1489 Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

The solutions assume some knowledge of Big O notation

The Problems

Each problem will be approached in turn, with a solution and also with articles explaining the tools, techniques and theory that will help you solve these problems yourself.

Let us get started!

1486. XOR Operation in an Array

This is a task around logical operators.

You are asked to return the bitwise XOR (which in Swfit is ^) of an array where each element is defined by nums[i] = start + 2 * i where start is the initial element in the array, and i is the index of the array.

Image for post
Image for post
Click for Gist

You could of course rewrite this as a recursive function.

1487. Making File Names Unique

Given an array of strings called names posessing size n there will be n unique names.

To ensure that each unique name is unique where there is a collision (k) is appended to the name of the file, using the smallest possible integer k to ensure that the solution is unique.

The unique names are passed in an array of Strings.

To keep the solution fast enough a dictionary is used since the access in a dictionary in Swift is O(n).

We traverse across the input names and see if they are in our dictionary (here called hash). This dictionary also stores the previous k value that has been stored when constructing the file which is returned in the output [String] (that is, array of Strings).

Image for post
Image for post
Click for Gist

1488. Avoid Flood in The City

This is a medium problem, so we start to get into more tricky problem territory.

There are lakes that can only be filled once. We are given an array of rainy days that will fill the appropriate lake with water (as defined by rains[i] for lake i). If rains[i] == 0 one lake (of your choice) can be emptied. Now the main part of this problem is that a lake can only be filled once (until emptied!) and would be flooded if there is no other option but to fill a lake multiple times (and an empty array [] would be returned). A valid answer is an array of Integer that for each element i, if rains[i] > 0 then ans[i] == -1 and if rains[i] == 0 then ans[i] becomes the Integer representing the lake that you choose to empty.

This problem must be completed quick enough to not get the dreaded “Time Limit Exceeded” error, and to enable this a dictionary is used to store each lake (and the day it is filled).

Now it makes sense that each lake can only be filled once — if this is not true we return the empty array.

It is tricky because you need to use an array for dryDays rather than a set because the “soonest” avalible dry day must be picked for any particular lake in order to avoid floods.

Image for post
Image for post
Click for Gist

1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

This last problem is given a weighting of 7 by LeetCode — meaning that it is quite tricky.

The solution requires looking at Kruskal’s Algorithm in Swift.

The graph is given to us as a set of Edges (startNode, weight, endNode) representing a weighted undirected connected graph with n verticies.

The basic algorithm is

  • Find the minimum using Kruskal’s algorithm (using union-find to detect cycles)
  • For each edge, if the the MST excluding this edge result in a higher weight, that edge is a critical edge. If the MST including the edge is the same weight as the minimum, it is added to the pseudo-critical edge list

We must calculate the Minimum Spanning Tree (MST) of this undirected graph (the algorithm here relies on a sorted array of edges), and make sure that the original index is used of the array (even though, as stated, they are sorted).

Calculate the minimum weight, and if edges are larger than this the are critical. Smaller edges are non-critical.

Here is the code:

Image for post
Image for post
Click for Gist

If you’ve any questions, comments or suggestions please hit me up on Twitter

Feel free to sign up to my newsletter

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store