Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Solution
We need to find the maximum sum contiguous subarray here. Let’s start from the example above. Let’s keep track of sum and maxSum which is a very small number N. And start summing from the beginning –
for -2, sum is -2, maxSum will still become -2.
sum of -2 and 1 will be -1, A thing to note here is our new sum -1 is less than the current value 1. So our sum should become 1 and max between -2 and 1 is 1. Therefore our maxSum is also 1.
sum of 1 and -3 is -2. maxSum between -2, 1 is 1.
sum of -2 and 4 is 2, which is less than 4. so sum becomes 4. and maxSum becomes 4.
And we keep doing this until we reach end.
Our basic algorithm will be
Take two variables sum and maxSum to keep track of sum and maxSum till a given position in array.
Loop through the array
sum is addition of sum and current value in the array. If sum < current value in the array, sum becomes current value in the array.
maxSum is maximum of maxSum and sum.
Repeat above steps until we reach the end of the loop.
return the maxSum
/**
* MaxSubArray.java
* Purpose: Find maximum sum contiguous subarray
*
* @author Megha Rastogi
* @version 1.0 06/06/2020
*/
class MaxSubArray {
/**
* Find maximum sum contiguous subarray
*
* @param Array, nums
* @return integer, maxSum
*/
public int maxSubArray(int[] nums) {
// Initalize maxSum and sum
int maxSum = Integer.MIN_VALUE, sum = 0;
// Loop through the array
for(int i = 0; i < nums.length; i++){
// add current value to sum
sum+=nums[i];
// update sum if it becomes less than current value
if(sum < nums[i])
sum = nums[i];
// update the max sum
maxSum = Math.max(maxSum, sum);
}
//return the max sum
return maxSum;
}
}
In our previous post, we stored the graph in Edges List and Vertices List. And we saw that time complexity of performing operations in this representation is very high. So, we need another representation which can perform operations in less time.
Another representation of the graph is a 2D array of size V x V called Adjacency Matrix. Let’s call that matrix adjacencyMatrix. If we have an edge between nodes s and d, then adjacencyMatrix[s][d] is set to 1 or weight, else set to infinity.
Unweighted Undirected Graph
Consider the following graph
The adjacency matrix of above graph is
There is an edge between 1 and 2, so we put 1 in adjacencyMatrix[1][2] and also in adjacencyMatrix[2][1] as this is an undirected graph. We give value 1 here because there is no weight for an edge. There is no edge between 1 and 3, so we put infinity in adjacencyMatrix[1][3].
In Java, we initialize a 2D array adjacencyMatrix[size+1][size+1], where size is the total number of vertices in the graph. For the above graph, the matrix will have a size of 7. We assign Integer.MIN_VALUE which is equivalent to negative infinity to adjacencyMatrix.
(Note: We can assign an index from 0 to 6 to all the vertices, but that creates confusion. Here, we use node names as the array index in this implementation. Since there is no node 0, and node start from 1, we increase the matrix size by 1. If you have string nodes, you can give them indices from zero and use size instead of size+1.)
public class GraphAdjacencyMatrix{
//2-D array to store adjacency matrix
private int[][] adjacencyMatrix;
//variable to store size of 2-D array/adjacency matrix
private int size;
//Constructor to initialize the matrix and size
public GraphAdjacencyMatrix(int size){
this.size = size;
adjacencyMatrix = new int[size][size];
for(int[] single : adjacencyMatrix)
Arrays.fill(single, Integer.MIN_VALUE);
}
}
Add an edge
Now we add edges between two nodes using the following method. Since the graph in fig 1 is undirected, we add an edge from source to destination and destination to source by assigning one to adjacencyMatrix[destination] and adjacencyMatrix[destination].
public void add(int source, int destination){
adjacencyMatrix[destination] = 1;
adjacencyMatrix[destination] = 1;
}
Find Adjacent Vertices
The findAdjacent method takes an index as input and returns anArrayList of verticesadjacent to the index. To find all adjacent vertices of the index, we need to traverseadjacencyMatrix[vertex] and add those vertices to list whose value is 1.
Since we traverse adjacencyMatrix[vertex] linearly, whose size is V (V being the number of vertices in the graph), the time complexity of this operation is O(V).
public ArrayList<Integer> findAdjacent(int index){
ArrayList<Integer> adjacent = new ArrayList<Integer>();
for(int i=1;i<size;i++){
if(adjacencyMatrix[index][i] == 1)
adjacent.add(i);
}
return adjacent;
}
Find whether two nodes are connected
To find whether source and destination are connected, we just check whether adjacencyMatrix[destination] or adjacencyMatrix[destination] is equal to 1. If any of them is equal to 1, source and destination are connected else they are not connected. The time complexity of this operation is O(1) as we only access a position in a 2D matrix.
public boolean isConnected(int source, int destination){
if(adjacencyMatrix[destination] == 1 || adjacencyMatrix[destination] == 1)
return true;
return false;
}
The entire code for a unweighted undirected graph is available here.
Weighted Undirected Graph
If an edge between source and destination has a weight then we assign value of weight to adjacencyMatrix[destination] and adjacencyMatrix[destination].
public void add(int source, int destination, int weight){
adjacencyMatrix[destination] = weight;
adjacencyMatrix[destination] = weight;
}
To find adjacent nodes of a given node, we add all those nodes to the list whose value is not equal to Integer.MIN_VALUE.
public ArrayList<Integer> findAdjacent(int index){
ArrayList<Integer> adjacent = new ArrayList<Integer>();
for(int i=1;i<size;i++){
if(adjacencyMatrix[index][i] != Integer.MIN_VALUE)
adjacent.add(i);
}
return adjacent;
}
Similarly to check whether two nodes are connected or not, we check whether adjacencyMatrix[destination] or adjacencyMatrix[destination] is not equal to Integer.MIN_VALUE.
public boolean isConnected(int source, int destination){
if(adjacencyMatrix[destination] != Integer.MIN_VALUE || adjacencyMatrix[destination] != Integer.MIN_VALUE)
return true;
return false;
}
The whole code for the weighted undirected graph can be found here.
Weighted Directed Graph
In case of directed weighted graph, we assign weight to onlyadjacencyMatrix[destination] and not to adjacencyMatrix[destination]. Other operations are same as those for the above graphs. The whole code for directed weighted graph is available here.
Problems in this approach
If we have a graph with million nodes, then the space this graph takes is square of million, as adjacency matrix is a 2D array. That’s a lot of space. It is good when we have a large number of vertices and equally large number of edges between them, as then we will have a dense matrix. But If we have a graph with a lot of vertices and very few edges, resulting in a sparse matrix, we store a lot of infinite values which are unnecessary and take a lot of space. The next implementation Adjacency List, which we cover in next post improves upon this.
A large number of vertices and equally large number of edges between them will produce a dense matrix. Here, using adjacency matrix is efficient. But a large number of vertices and very few edges between them will produce a sparse matrix. Here, using adjacency matrix is inefficient as we store a lot of infinite values (taking up large space) which are unnecessary. The next implementation Adjacency List, which we cover in next post improves upon this.
In the previous post, we explained what are graphs and how the graph is represented mathematically. In this post, we see how to represent that Graph in computer’s memory (means which data structures to use to implement graphs).
Graphs can be represented in three ways:
Edges and Vertices List.
Adjacency Matrix
Adjacency List
In this post, we start with the first method Edges and Vertices list to represent a graph.
Edges and Vertices List
Here a graph is represented as a vertices list and edges list. The list here means we can use an Array or an ArrayList in Java to store the vertices and edges separately.
Consider above graph, the vertices can be stored in a vertices array and the edges can be stored in a separate array.
Vertices are stored using an array of integers directly. But an edge {u,v} has two values which can’t be stored directly in an array. Therefore we create a class Edge with two instance variables to store the name of the two vertices. Here {1,2,3,4,5,6} are names of our vertices. We could use strings also instead of integers for the names of vertices.
/**
* Edge --- class to store an edge between Start vertex and End vertex
*/
class Edge{
private int startVertex;
private int endVertex;
public Edge(int startVertex, int endVertex){
this.startVertex = startVertex;
this.endVertex = endVertex;
}
//Getter method for start vertex
public int getStartVertex(){
return startVertex;
}
//Getter method for end vertex
public int getEndVertex(){
return endVertex;
}
}
We know that the graph is undirected, so if an edge {u.v} exists, then edge {v,u} exists. But to store edge {v,u} is futile as that will take only extra space. We assume that if we add an edge {u, v} we are also accounting for the edge {v, u}.
Instead of arrays, we are using ArrayList in our implementation as it is more dynamic. So there are two ArrayLists, one of Integer type to store vertices and another of Edge type to store edges.
//List verticesList to store vertices
private static ArrayList<Integer> verticesList;
//List edgesList to store edges
private static ArrayList<Edge> edgesList;
Add an edge
Next, we see how to add an edge from any vertex to another vertex. The following add method does exactly that. First, we check whether the start vertex is present in our verticesList, if not we add it. Then we add an edge object containing both start and end vertex to the edgesList. This way both our verticesList and edgesList are filled simultaneously, ie. stored our entire graph.
public void add(int start, int end){
if(!verticesList.contains(start)){
verticesList.add(start);
}
edgesList.add(new Edge(start, end));
}
Find Adjacent Vertices
Now that we have created our graph lets perform some operations on them. The first one is to find adjacent vertices of a given vertex. Adjacent vertices are those vertices to which we have an edge from the given vertex. For example, in the above graph, adjacent vertices of 1 are 2, 4, 5 as there are edges to 2, 4 and 5 respectively from 1.
The findAdjacent method takes a vertex as input and returns an ArrayList of verticesadjacent to the vertex. To find all adjacent vertices of vertex, we need to traverse all edges in the edgesList to check which edge contains vertex. If an edge contains vertex, we add the corresponding vertex of that edge to our adjacent list.
If startVertex is equal to vertex we add the endVertex to the list and if endVertex is equal to vertex we add startVertex to the list. In the end, we return the adjacent list.
If there are E edges then the worst case time complexity of this method will be O(E). Because to find adjacent of any vertex we are traversing through all the edges.
Find whether two nodes are connected
Two nodes are connected when they have an edge between them. Here also we traverse the whole edgesList and check whether vertices of each edge are equal to the given set of nodes or not. If we have a match then the two nodes are connected, otherwise, the two nodes are not connected.
public boolean isConnected(int start, int end){
for(Edge edge: edgesList){
if((edge.getStartVertex() == start && edge.getEndVertex() == end) ||
(edge.getStartVertex() == end && edge.getEndVertex() == start))
return true;
}
return false;
}
If there are E edges then the worst case time complexity of this method will also be O(E).
The entire code for this undirected unweighted graph is available here.
Weighted Undirected Graph
If the edges have a weight associated with them then we add another instance variable of integer type to the edge class to store the weight of that edge. And rest operations like adding the edge, finding adjacent vertices of given vertex, etc remain same. The code for a weighted undirected graph is available here.
/**
* Edge --- class to store an edge with a weight between Start vertex and End vertex
*/
class Edge{
private int startVertex;
private int endVertex;
private int weight;
public Edge(int startVertex, int endVertex, int weight){
this.startVertex = startVertex;
this.endVertex = endVertex;
this.weight = weight;
}
//Getter method for start vertex
public int getStartVertex(){
return startVertex;
}
//Getter method for end vertex
public int getEndVertex(){
return endVertex;
}
}
Weighted Directed Graph
The entire representation of graph will be same as the undirected graph. Only the way to access adjacent list and find whether two nodes are connected or not will change. Because now we only have an edge (u,v). The code for the weighted directed graph is available here.
Why this implementation is not effective
For this implementation, we store the graph in an Edges List and a Vertices List. First, consider the space used in this representation. The first Vertices List is a simple integer array of size V (V is a total number of vertices in the graph). If we assume the integer takes constant space ie, O(1), then space to store V vertices will be O(V * 1) ie O(V). The second Edges List is an array of edge objects, and each edge object stores two or three integer variables. Therefore, each edge takes constant space, as we assume both integers takes constant space, ie O(1). If there are E edges then the space for Edges List is O(E). The total spacecomplexity of this representation is O(V + E).
We already know the time complexity of some operations from above, ie O(E). We traverse linearly through all edges to get our desired result. And the number of edges in a graph can be as high as V*V in the worst case. Which makes the time complexity of operations very high.
So, we need an implementation which has operations run in order of vertices instead of edges. In the next post, we study another way to store graph, ie Adjacency Matrix.
Now that we have learned arrays and sets, it’s time to finish collections by learning dictionaries.
Dictionaries. What do you think about when you hear the word dictionary. Well, I think about the dictionaries, the English dictionaries we used when we were kids to find the meaning of words. I use them still. Just that the dictionary is now on the internet.
Think about how we used to search a meaning of the word, for example, “rock” in the dictionary. We will straight away go to the r section of the book, then search for a word starting with “ro” and finally zero in on our word rock. Read its meaning and close.
We wouldn’t start with words starting with a, followed by b, and so on to reach the words starting with “r”. That is going to take a lot of time. Am I right? We will just straight away jump to the words starting with “r”
One important thing to note here is that rock is the key and its meaning is the value. We find the key, we find the meaning.
Just like those English dictionaries, dictionaries in swift are generally pairs/associations of keys and values. These keys and values can be of the same type or different. Also, every value is associated with a key, which is now an identifier for that value.
Like sets, dictionaries also have no ordering.
A dictionary is written as [“key” : “value”]
Example, a dictionary of antonyms : [“hot” : “cold”, “dark” : “light”, “big” : “small”]
Here “hot’ will be a key and “cold” its value.
The swift dictionary type is written using Dictionary[“Key” : “Value”]. This can also be written as [“Key”: “Value”]. The latter form is widely used.
Coming back to the playground, let’s learn how to initialize and use these dictionaries.
The first method, just like in arrays and sets, uses the initializer syntax.
Here we will use the antonyms example.
var antonyms = [String : String]()
This will generate variable antonyms which can store keys of type String and values also of type string. Currently, it is initialized as an empty dictionary.
Let’s print this and see
print(antonyms)
This symbol here [:] shows the dictionary is empty.
Now comment this line and the print line and again initialize the dictionary as empty.
var antonyms = [:]
This throws an error “Empty collection literal requires an explicit type”
This happens because the compiler doesn’t know the type of key and values. So we cannot use this way to initialize a dictionary.
When we uncomment our first line. Then remove “var” from this one the error vanishes.
Let’s add few antonyms to our dictionary. And remove the comment from print statement.
Well, now we know how to initialize the dictionary. so let’s have a look at the operations we can perform on it.
The first operation is “Insert”
We use subscript syntax to insert into dictionaries. In this method, we will use a new key having the same type as Keys and assign to it new value having the same type as Values.
Now we will add tomatoes and squash to our dictionary.
A set is just like an array. Only the difference being that sets have distinct values and no ordering.
example: A set of first four letters of an alphabet. [“a”, “b”, “c”, “d”]
How do we initialize a set in Swift?
We do the initialization using initializer syntax:
Let’s initialize a set containing ages of our friends.
var age = Set<Int>()
var age followed by Set, Int in open brackets, ending with function brackets.
When we print age, we see that it’s empty.
So, we need to add in the ages using
age = [38, 65, 97]
Now when we print age, we see it has three numbers 38, 65, 97.
The second method of initialization is using array literal.
For this one, we will use an array of colors.
var color : Set<String> = ["Red", "Green", "Yellow"]
The variable color is declared as a set if string values are written using Set<String>. The variable color can only save String values as we specified the type as String. Since we used three colors to initialize the set, color set is not empty.
In arrays, we used [String], but here we use Set<String> as Set type can not be inferred only with String in double brackets, word Set is very important.
This initialization can be done using only “Set” as Swift can infer the type of elements of the set because of its type inference property.
First commenting this initialization, we write
var color : Set = ["Red", "Green", "Yellow"]
Next, we work upon the “Operations on Set”
The first operation is “Inserting an element into the set“. For this, we will insert color “Blue” in the set “color”.
color.insert("Blue")
We can see here in the result bar that “Blue” has been added to set “color”
To confirm, we can print color.
A difference from the array can be seen here, we have not specified the location where we want the blue to be placed. Because unlike arrays, sets are unordered lists. So blue is added at a random position.
The subsequent function is “Removing an element from the set“. For this, we will remove color “Green” from the set.
color.remove("Green")
When we print the set now, the result is devoid of “Green”.
Now we move on to “Contain function: to check whether an element is inside the set”. Again for this first, we will check whether alphabet “a” is inside set and then check whether “Red” is inside the set.
print(color.contains("a"))
We can see the result here in the result are is “false” as “a” is not inside set color.
print(color.contains("Red"))
Red is inside set the color and so the result is true.
Next is the method to count the number of elements in the set.
print(color.count)
Clearly, the answer is 3 as seen here.
Apart from all these operations, there are certain operations that are performed on sets as we have studied in maths.
Let’s see one by one all the operations:
Consider two sets :
A = { “a”, “e”, “i”, “o”, “u” }
B = { “l”, “a”, “u”, “r”, “e”, “n” }
The two circles here denote sets A and B.
Since { “a”, “e”, “u”} is common in two sets, we place them in the intersecting of two circles.
{ “a”, “e”, “u”} is also the result of intersection of sets A and B. The yellow color is used to highlight An intersection B
Union operation on the sets leads to a set of all elements from A and B.
So here union of set A and B will have {“a”, “e”, “i”, “o”, “u”, “l”, “r”, “n”} with { “a”, “e”, “u”} only once. As we have seen earlier sets cannot have repeated values, hence no repeated values here.
On this slide, the yellow color is used to show the union of sets A and B.
Symmetric Difference gives values in each set but not in both. Here they will be { “o”, “i”, “l”, “r”, “n”}
Subtracting B from A will give values in A which are not in B. ie { “o”, “i” }
Now we will perform all these operations in Swift.
We have taken two sets:
var vowels : Set = ["a", "e", "i", "o", "u"]
var nameLetters : Set = ["l", "a", "u", "r", "e", "n"]
The first operation is Intersection
print(nameLetters.intersection(vowels))
The result is { “a”, “e”, “u”} as expected
Next is Union
print(nameLetters.union(vowels))
The result is all letters in both sets : [“a”, “i”, “r”, “n”, “u”, “e”, “l”, “o”]
For Symmetric Difference
print(nameLetters.symmetricDifference(vowels))
we get [“o”, “l”, “r”, “i”, “n”] as expected
The last is subtraction
print(nameLetters.subtracting(vowels))
The result is [“l”, “r”, “n”] as expected.
With this we complete Sets. In next post, we will cover Dictionaries, the last of collections.
Append, Insert, Remove, Count, and Retrieve are the operations that can be performed on arrays.
Append is used to add items at the end of an array. Here we are adding “Ravenclaw” to the array “house”. Ravenclaw is added to the end of the array.
Insert is used to add items at a desired position in the array.
“insert(newElement: Element, at: Int)
Here newElement is the element we want to add in the array. And after at: we specify the index at which element will be added.
In our example, we are adding “Slytherin” and index 1. Array index start from 0, so Slytherin gets added after Gryffindor which is at 0. Rest elements are shifted one place down.
Remove is used to delete items in the array.
“remove(at: Int)”
Here we just need to specify the index of the element we want to delete.
In our example we are deleting “Slytherin” which is at 1.
Count returns the total number of items in the array.
We can retrieve any element of the array through its index. Here we want to access Ravenclaw. So we use the index of Ravenclaw.