— Diary, Programming — 2 min read
This seems to be getting a lot infrequent but I started learning Kotlin for Android Development. For now, let's complete the Leetcode Challenge. THe question is a graph coloring problem where the two in an edge have to be of different colors.
The question has a very straightforward approach. Pick a node, color it with one of the colors, and paint its neighbors with the other color, and continue this till all the nodes are colored. If by any change the graph is a disconnected one, check for the queue empty condition and see if there are any unvisited nodes.
1bool isBipartite(vector<vector<int>> &graph) {2 vector<int> m(graph.size(), -1);34 m[0] = 1;5 queue<int> q;6 q.push(0);78 while (!q.empty()) {9 int u = q.front();10 q.pop();1112 for (auto a : graph[u]) {13 if (m[a] == -1) {14 m[a] = 1 - m[u];15 q.push(a);16 } else if (m[a] == m[u]) return false;17 }1819 if (q.empty()) {20 for (int i = 0; i < m.size(); i++) {21 if (m[i] == -1) {22 m[i] = 1;23 q.push(i);24 break;25 }26 }27 }28 }2930 return true;31}Time complexity O(n) where n is the number of nodes in the graph. Space complexity is O(n) if the first node connects to all the other nodes.
Since my root partition in Ubuntu was running out of disk space and was causing a lot of issues, I had to reinstall Ubuntu. So I backed up all the important config files to get started ASAP.
I am thinking about creating a git repository with all the necessary files, so that I can get started even if I don't have the backup physically available.
The setup procedure of Android studio took a while with all the installing that had to be done. But finally it is working and I can start by learning the syntax of Kotlin and then making some basic stuff. What I would love though is making a replica of SayInEditor with Kotlin.
Time for some sleep!
I have to make a Schedule section for the HackOn website and the design was given by haxzie this morning only. Since there is no schedule currently, this section won't be published right away and I have a lot of time to get it done.
Let's start and see what issues arise. The most important thing that I have learned while working on this project is the dispaly: flex and probably will never forget it, so that's a good thing.
I am done with the basic UI for the section but still have to make it responsive. The only issue right now is that the design will not look very good on mobile devices. So I'm thinking about removing the more details button on mobile phones and making the image smaller.
For now, I'll push it in a separate branch since it is not required until the schedule is decided.
Back to work! I think it's time to take a look at today's Leetcode challenge.
The approach is just counting the number of ones in each row and the inserting the pair<ones, index> in the min heap. After that, all that's left to do is to get k minimum elements from the heap.
1vector<int> kWeakestRows(vector<vector<int>> &mat, int k) {2 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;34 for (int i = 0; i < mat.size(); i++) {5 int ones = 0;6 for (auto j : mat[i]) {7 if (j == 1) ones++;8 else break;9 }10 pq.push(make_pair(ones, i));11 }1213 vector<int> ans;14 while (k--) {15 pair<int, int> tp = pq.top();16 ans.push_back(tp.second);17 pq.pop();18 }1920 return ans;21}Time complexity O(m*n) where m and n are the number of rows and columns respectively. Space complexity is O(m) to store in priority_queue.
Made the HackOn Website Schedule section responsive and pushed. Will have to deploy on netlify manually.
Good night!