Header image: Photo by Roman Arkhipov on Unsplash
Preface
This post will cover the New Year Chaos HackerRank challenge covering arrays. It will also apply the bubble sort algorithm, which I've talked about previously here.
Note: Too lazy to read? Here are the goods on PythonTutor
The Problem
People are waiting in line, each individual is represented by an integer at an index. If everyone is honest, each individual would be at the index that is 1 less than their value i.e. first person is at 0, second at 1, etc...
If the line gets messy, and say person 7 is at index 0, and 4 is at index 6, we need to figure out how many "swaps" need to happen minimally to restore order.
Obviously, we can't just look at a number and place them into a new array at an index that is one less of the value. The problem is asking for the amount of swaps, not a sorted array.
The Caveat
If a person needs to swap more than twice, the line is declared "Too chaotic". This will be our secondary break mechanism.
The Core
Bubble sort at the core, missing ways to keep tracking of total amount of bribes and if an element has been swapped more than twice or not.
function minimumBribes(q) {
//add variables to keep track of bribes
while (k > 0) {
let noSwap = true
for (let i = 0; i < k; i++) {
//add ways to keep track of how many times an element is swapped
//reset this count if no swap happens when moving on to the next
element
let j = i + 1
if (q[i] > q[j]) {
noSwap = false
swapValues(q, i, j)
}
}
if (noSwap) break
k--
}
//return the total swaps here.
}
function swapValues(array, i, j) {
[array[i], array[j]] = [array[j], array[i]]
}
Now with the added counters and logic to break if things are "Too chaotic":
function minimumBribes(q) {
let k = q.length
let totalBribes = 0
//currentSwaps will keep track of how many times an element has been swapped
let currentSwaps
//noSwap is the standard flag to break the loop if array is already sorted
let noSwap
while (k > 0) {
//assumes initial values
currentSwaps = 0
noSwap = true
for (let i = 0; i < k; i++) {
let j = i + 1
if (q[i] > q[j]) {
/*if an element at `i` is already swapped twice, we know this
crazy line is "Too chaotic". Break out and save our sanity. */
if (currentSwaps == 2) {
console.log("Too chaotic")
return
}
/* if that's not the case, we swap and increment both counters
by 1, also set the noSwap flag to false,
so next iteration can happen to check if array is sorted */
noSwap = false
swapValues(q, i, j)
++currentSwaps
++totalBribes
//if no swap happens, we reset currentSwaps for the next new element
} else {
currentSwaps = 0
}
}
if (noSwap) break
k--
}
console.log(totalBribes)
}
function swapValues(array, i, j) {
[array[i], array[j]] = [array[j], array[i]]
}
Hope this makes sense. Let me know if I screw up somewhere, happy to revise.
BONUS: First attempt at the problem
function minimumBribes(q) {
let bribes = 0
for (let i = 0; i < q.length; i++) {
//if the element at index i is greater than it's current index + 3, we
//know it'll be "Too chaotic" to fix
if (q[i] > i + 3) {
console.log("Too chaotic")
return
//else, add to bribes the difference between the the current element's
value and the next index value (i.e. element 7 at index 3)
} else if (q[i] > i + 1) {
bribes += q[i] - (i + 1)
//sometimes, the current element is is smaller than it's index (i.e.
element 4 at index 6)
} else if (q[i] > q[i + 1]) {
bribes++
}
}
return console.log(bribes)
}
This passed the initial 3 test cases, but failed all the others and gave me a big headache!
Top comments (0)