₦airaland Forum

Modified and refactored solution, hard to test since there are multiple valid solutions for a testcase.

def partitionHelper(arr, pivot):
    i, j = 0, len(arr) - 1
    while i < j:
        while i < len(arr) and arr[i] <= pivot:
            i += 1
        while j >= 0 and arr[j] > pivot:
            j -= 1
        if i > j:
            break
        arr[i], arr[j] = arr[j], arr[i]
        i, j = i + 1, j - 1
    return j


def move_till_not_pivot(arr, i, j, pivot):
    while arr[j] == pivot:
        j -= 1
        if j < 0 or j <= i:
            return -1
    arr[i], arr[j] = arr[j], arr[i]
    return j - 1
    

def partition(arr, x):
    i, j = 0, partitionHelper(arr, x)
    while i < j:
        if arr[i] == x:
            j = move_till_not_pivot(arr, i, j, x)
        i += 1
    return arr

GREATIGBOMAN:
Yesterday?

U posted the question on 30th


Abi u meant u arrived at the solution yesterday @ 5pm exactly:

Oh it's 30, I posted @ 7: 19pm, 2hrs+ is a reasonable time frame to solve these types of questions.

Luckydonalds:
While your solution may get the job done ( I didn't test it, but I looked through it to understand it well enough), I hate to be the one to break it you that it doesn't satisfy the time constraint. It has a time complexity of O(n**2) but your question requested for O(n).

It's O(n), it's just two pointers all around.

GREATIGBOMAN:
So many nested loops and exponential increase.


How does this satisfy your question which should be 0(n)

It's actually O(n), the first part is just the normal quicksort's partitioning algorithm, the second part builds on that.

GREATIGBOMAN:
Yea... just saw where he used breaks and it seems no value increase more than one.


The way he posted it it seems he's spent more than a week with the question self

I actually received the question yesterday around 5pm, it's from daily coding problem.

Najdorf:
His code is actually O(n). Nested loops ≠ exponential increase always.

But OP your code fails to some test cases e.g [9,4,10,12,10,23,5,10,90,5] with pivot of 10

Yeah just noticed, it's subtle,
bug 1: apparently we should only swap while i < j in the second
part.
bug 2: we should stop when i and j becomes equal in the first
part.

TastyFriedPussy:
too you this long only to copy and paste the answer? most of you claiming programmers in the section are nothing but a bunch of jokes

You cannot troll me boss, just don't try.

Playermayweda:
Make una no beat me oo, but what if you create three different array from the initial array containing the different values mentioned in the problem. You can filter each array based on the requirements of the problem and merge the three arrays.

Is it a must it should be constant space?

I also don't think my solution is O(n2) rather O(n).

Na question I ask make una no beat me oo

It's O(n), but this approach has been discussed many times before.

CyberHustle:
Modifying my first solution based on how I understand the constraint.

Sort the main array, loop through it until you get to where values equalling X starts. Store that index minus 1 as an integer of where values below X stops. Continue looping until a value above X is encountered and store the index of that as another integer value.

That leaves us with one new sorted array with size n and two int values to identify values less than and greater than X.


Cc: najdorf.

Sorting the array only is a valid solution, only issue is the n log n runtime.

It's been a while, so this my solution.
The approach is to simply partition the array using quicksort's partitioning algorithm, but with the new constraint:
• All elements to the left of the pivot must be less than or
equal to the pivot.
• All elements to the right must be greater.
for example:
arr = [3,2,5,7,4,5,1,10]
x = 5
result would be like => [2,3,5,4,1,5,7,10].

we know the index of last pivot element in the arr, we do 2 pointer swaps from index 0 to index of the pivot, in code:

def partition(arr, x):
  i, j = 0, len(arr) - 1
  while i <= j:
    while i < len(arr) and arr[i] <= x:
      i += 1
    while j >= 0 and arr[j] > x:
      j -= 1
    if i > j:
      break
    arr[i], arr[j] = arr[j], arr[i]
    i, j = i + 1, j - 1
  
  i = 0
  while i < j:
    if arr[i] == x:
      while j >= 0 and arr[j] == x:
        j -= 1
      arr[i], arr[j] = arr[j], arr[i]
      j -= 1
    i += 1
  return arr

Enceladus:
two pointers solves this in O(n) at worst. This is probable the first question to wet your appetite. It's suspiciously easy.

If it's that easy then explain your approach.

bushjeph:
what branch of subject i mean?

Arrays, 2 pointers, partitioning, quicksort.

bushjeph:
What sort of question be this?

The type that Amazon asks ,
too hard?

salvationproject:
May not be the most efficient way of doing this in JS but it is very much effective.


function partitionArray(array, x)
{
let lArray = [], eArray = [], gArray = [];
for (let i = 0; i < array.length; i++)
{
let v = array[i];
if (v < x)
{
lArray.push(v);
}
else if (v == x)
{
eArray.push(v);
}
else
{
gArray.push(v);
}
}
return lArray.concat(eArray).concat(gArray);
}

alert(partitionArray([9, 12, 3, 5, 14, 10, 10], 10));

Space complexity to beat is O(1), this constraint is what actually makes it a difficult FAANG level problem else just sorting the array would work too.

GREATIGBOMAN:
Can't believe Amazon ask such questions

Too hard or too easy?

Luckydonalds:
Do you mean the we should modify the array passed to the function directly?

Yes, 2 pointers come into play in these context.

Since constant space is required, no additional data structure's allowed.
I was able to come up with a solution by modifying the quicksort's partitioning algorithm, so that's a hint.

tensazangetsu20:
You can solve this using quick sort.

function QuickSort(Arr, x){
if(Arr.length <= 1){
return Arr;
}

const pivot = x
const leftArr = [];
const rightArr = [];

for(let i=0; i < Arr.length-1;i++){
Arr[i] < pivot ? leftArr.push(Arr[i]) : rightArr.push(Arr[i])
}

return [...QuickSort(leftArr, leftArr[leftArr.length-1]) ,pivot,...QuickSort(rightArr, rightArr[rightArr.length -1])];

}

console.log(QuickSort([9, 12, 3, 5, 14, 10, 10], 10))

Sure but the runtime to beat is O(n), that's the challenging part of the problem.

This problem was asked by Amazon.

Given a pivot x, and a list lst, partition the list into three parts.
* The first part contains all elements in lst that are less than x
* The second part contains all elements in lst that are equal to x
* The third part contains all elements in lst that are larger than x
Ordering within a part can be arbitrary.
For example, given x = 10 and lst = [9, 12, 3, 5, 14, 10, 10],
one partition may
be [9, 3, 5, 10, 10, 12, 14].

Can you solve it in strictly O(n) time and O(1) space complexity?
I'd like to see what you come up with.

@qtguru
@deicide
I agree according to the standard definition, C++ is high level.
To a bullet a car is slow, but to a human a car is fast, saying C++ is low level is not completely wrong, that's the point I'm pushing.

Hannania:
HNG is just a training I guess. I won't tag that an internship since you only build imaginary projects but not working on live projects

Sure, but there's still relatively more part-time internships, IBM sometimes do offer them.

Deicide:
That's not how it works. If you understand what the definition of A high level language is. Though I get your point.

Like I said it's relative, compared to assembly yes C++ is a high level language, but to python it's not.
Low level can means different things in different contexts, so I get your point.

qtguru:
Wrong, anytime low level is used, it means closer to CPU instructions ( MOV, ADD, SUB), Assembly is low level, C++ is still High level

Yes low level means closer to CPU instructions, manually managing memory with pointers is a much lower-level operation than just setting variables.
Just because assembly is closer to the hardware doesn't disqualify C++, atleast imo, together with many other devs online. plain binary by default is lower than assembly but it doesn't disqualify assembly.

Hannania:
Who takes interns on part-time? It was fulltime

Major league hacking/hng offer part-time internships, but 50k for full-time is just disrespectful.

sqlPAIN:
I barely see any real programmers on this section. majority of the people who call themselves programmers on this section are mostly mere web developers or data analysts. I barely see peeps talk about low level programming languages, or even talk about any other field in tech apart from web development.


sqlPAIN

web dev, mobile dev and data is where the money at, most of we Nigerians devs do this for the money, but yeah these domains are mostly boring, except for maybe backend development.

Deicide:
If you think C++ is a low level programming language then you probably don't know anything.

The term low level is relative, yes compared to langs like python/javascript c++ is low level.

Hannania:
It's Flexisaf, they pay interns 50k

part-time or full-time?

Hannania:
Valid Parentheses come to mind right now

exactly

Peterpan007:
See the question I was asked

This is valid parentheses in disguise, simplifying the input should work, something like:

import re

def solve(s):
  html_elems = set("b i div em p".split())
  tokens = re.sub("[<>]"," ", s).split()
  stack = []
  for token in tokens:
    if token in html_elems:
      stack.append(token)
    elif token[1:] in html_elems:
      if stack == []:
        return token
      elif stack[-1] != token[1:]:
        return token[1:]
      else:
        stack.pop()
  return stack[0] if stack != [] else True

obimerchant:
I am really wowed by all this I am seeing here...
really thought I was a good developer but nah....
can't even understand all this things you all are posting here

It's all core DSA, you might be a good developer but who knows, depends on your domain.

Guontey:
You can write it in one line of code if you can import Counter

a = [1,2,6,2,3,7,7,5,7,6,2,7]
from collections import Counter
list(list(zip(*Counter(a).most_common()))[0])

+1 for the Counter component, but the resulting code's really hard to read especially to non python devs, reason I wrote it plainly.

truthsayer009:
You can use TreeMaps which are ordered, you can also sort the maps after your logic. This problem is an easy one to be fair, if i see this type of problem in an interview. I will be praising the name of the Lord.

The runtime would still be O n log n but yeah you're correct and yes it's a simple question, that's why I had to post it.