Sort employees by salary, then experience

73.2k
0

A list of employee records is given. Each employee record contains two integer values: salary and experience.

Rearrange the complete list in non-decreasing order of salary. If two employees have equal salary, arrange equal-salary employees in non-decreasing order of experience. Return the sorted list of employee records.

Example 1

Input: employees = [[50000, 3], [40000, 5], [50000, 1], [40000, 2]]
Output: [[40000, 2], [40000, 5], [50000, 1], [50000, 3]]
Explanation: Salaries 40000 appear before salaries 50000. Among equal salary 40000, experience 2 appears before experience 5. Among equal salary 50000, experience 1 appears before experience 3.

Example 2

Input: employees = [[60000, 4]]
Output: [[60000, 4]]
Explanation: A single employee record already satisfies the required order.

Brute Force Approach

The easiest way to learn the ordering rule is to place the next smallest employee record one position at a time. Salary is checked first because salary has the highest priority. Experience is checked only when salaries are equal.

During every pass, the unsorted suffix is scanned. The best employee record is selected for the current boundary. A swap moves the selected record into the growing sorted prefix.

The comparison feels simple after the small rule becomes clear: lower salary wins first, and lower experience wins only during a salary tie.

Algorithm

  • The number of employee records is stored in n so every boundary position can be processed.

  • Every boundary from 0 through n - 2 is treated as the next position requiring the smallest remaining employee record.

  • An index named minIndex is initialized with the boundary because the boundary record is the first available candidate.

  • The remaining suffix is scanned from boundary + 1 through n - 1 so every unplaced employee record can be compared.

  • minIndex is updated when a smaller salary is found, or when equal salaries have smaller experience.

  • The selected employee record is swapped with the boundary record after the scan, so the sorted prefix grows by one record.

  • The sorted employee list is returned after every required boundary has been processed.

Dry Run

Image 1

Image 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function sorts employee records through repeated selection.
vector<vector<int>> sortEmployees(vector<vector<int>> employees) {
int n = employees.size();
// Each boundary marks the next sorted position.
for (int boundary = 0; boundary < n - 1; boundary++) {
int minIndex = boundary;
// Remaining employee records are scanned to find the best candidate.
for (int index = boundary + 1; index < n; index++) {
bool hasSmallerSalary = employees[index][0] < employees[minIndex][0];
bool hasEqualSalary = employees[index][0] == employees[minIndex][0];
bool hasSmallerExperience = employees[index][1] < employees[minIndex][1];
// Candidate changes when salary is smaller or salary tie is improved.
if (hasSmallerSalary || (hasEqualSalary && hasSmallerExperience)) {
minIndex = index;
}
}
// A swap is useful only when a different employee record was selected.
if (minIndex != boundary) {
swap(employees[boundary], employees[minIndex]);
}
}
return employees;
}
};
// Driver code
int main() {
// Input array
vector<vector<int>> employees = {{50000, 3}, {40000, 5}, {50000, 1}, {40000, 2}};
// Solution object creation
Solution obj;
// Result printing
vector<vector<int>> result = obj.sortEmployees(employees);
for (int index = 0; index < result.size(); index++) {
cout << "[" << result[index][0] << ", " << result[index][1] << "]";
// Separator is printed only between neighboring records.
if (index + 1 < result.size()) {
cout << " ";
}
}
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the number of elements in the array, because each boundary position scans the remaining unsorted suffix. The number of comparisons is (N - 1) + (N - 2) + ... + 1.

Space Complexity: O(N), because a copied employee list is stored before rearrangement.

Better Approach

Manual selection repeatedly scans the unsorted suffix. Merge sort removes the repeated scans by dividing the employee list into smaller ranges, sorting both ranges, and joining the sorted ranges in one pass.

During merging, salary decides the earlier record first. Experience is checked only after matching salaries. Choosing the left record for a complete tie preserves the earlier relative order while every salary-experience pair moves as one unit.

Algorithm

  • Begin with a copied employee list and one temporary list of equal size, so record movement leaves the caller-owned input unchanged.

  • Split every range around the middle until each range contains at most one employee record, because a single record is already sorted.

  • Sort the left and right ranges recursively, so the merge step always receives two ranges already following the required order.

  • Keep one pointer in each sorted range and compare salary first, because salary has priority in the final arrangement.

  • Compare experience only after equal salaries, and choose the left record for a complete tie to preserve stable ordering.

  • Copy the smaller record into temporary storage and move the matching pointer, so salary and experience remain connected throughout merging.

  • Copy any remaining records because one range can still hold the largest ordered records, then write the merged range back and return the list after the top-level merge.

Dry Run

sort-employees-by-salary-then-experience-better-approach

sort-employees-by-salary-then-experience-better-approach

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Merges two sorted employee ranges.
void mergeRanges(vector<vector<int>>& employees,
vector<vector<int>>& temp,
int left, int middle, int right) {
int first = left;
int second = middle + 1;
int write = left;
// Both ranges are merged in salary order.
while (first <= middle && second <= right) {
// Salary leads and experience breaks ties.
if (employees[first][0] < employees[second][0] ||
(employees[first][0] == employees[second][0] &&
employees[first][1] <= employees[second][1])) {
temp[write] = employees[first];
first++;
} else {
temp[write] = employees[second];
second++;
}
write++;
}
// Remaining left records already follow order.
while (first <= middle) {
temp[write] = employees[first];
first++;
write++;
}
// Remaining right records already follow order.
while (second <= right) {
temp[write] = employees[second];
second++;
write++;
}
// Merged order replaces the current range.
for (int index = left; index <= right; index++) {
employees[index] = temp[index];
}
}
// Recursively sorts one employee range.
void mergeSort(vector<vector<int>>& employees,
vector<vector<int>>& temp,
int left, int right) {
// A range of size zero or one is sorted.
if (left >= right) {
return;
}
int middle = left + (right - left) / 2;
// Both halves become ready for merging.
mergeSort(employees, temp, left, middle);
mergeSort(employees, temp, middle + 1, right);
// Sorted halves form one sorted range.
mergeRanges(employees, temp, left, middle, right);
}
public:
// Sorts employee records using merge sort.
vector<vector<int>> sortEmployees(
vector<vector<int>> employees) {
int n = employees.size();
vector<vector<int>> temp(n, vector<int>(2));
// The full range contains every record.
mergeSort(employees, temp, 0, n - 1);
return employees;
}
};
// Driver code
int main() {
vector<vector<int>> employees = {
{50000, 3}, {40000, 5}, {50000, 1}, {40000, 2}
};
Solution obj;
vector<vector<int>> result = obj.sortEmployees(employees);
for (int index = 0; index < result.size(); index++) {
cout << "[" << result[index][0] << ", "
<< result[index][1] << "] ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), because merge sort uses O(log N) levels and merges all N employee records once per level.

Space Complexity: O(N), because temporary storage holds N employee records and the recursion stack holds O(log N) calls.

Optimal Approach

Manual selection explains the ordering rule, but repeated full scans are slow for large input. Sorting libraries already perform efficient comparison sorting. The only special part is the comparator.

The comparator checks salary first. A record with a smaller salary must appear earlier. If salaries match, experience becomes the tie-breaker. The employee record still moves as one complete unit.

The solution becomes compact: copy the records, give the sorting routine a salary-experience rule, and return the sorted copy.

Algorithm

  • A copy of the employee list is created so caller-owned input does not need to be changed.

  • A comparator or sorting key is prepared to compare employee records by salary first.

  • Experience is used only when salaries are equal, so tie records receive a deterministic order.

  • The language sorting routine is applied to the copied list using the custom comparison rule.

  • During sorting, employee record positions are rearranged while salary and experience from the same record stay together.

  • The sorted employee list is returned after the library routine finishes all comparisons and placements.

Dry Run

Image 1

Image 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function sorts employee records with a custom comparator.
vector<vector<int>> sortEmployees(vector<vector<int>> employees) {
sort(employees.begin(), employees.end(), [](vector<int> left, vector<int> right) {
// Equal salaries are ordered by experience for deterministic output.
if (left[0] == right[0]) {
return left[1] < right[1];
}
return left[0] < right[0];
});
return employees;
}
};
// Driver code
int main() {
// Input array
vector<vector<int>> employees = {{50000, 3}, {40000, 5}, {50000, 1}, {40000, 2}};
// Solution object creation
Solution obj;
// Result printing
vector<vector<int>> result = obj.sortEmployees(employees);
for (int index = 0; index < result.size(); index++) {
cout << "[" << result[index][0] << ", " << result[index][1] << "]";
// Separator is printed only between neighboring records.
if (index + 1 < result.size()) {
cout << " ";
}
}
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), because the built-in sorting routine performs comparison sorting over N employee records.

Space Complexity: O(N), because a copied employee list is stored before sorting. Extra internal sorting space depends on the language runtime, but the copied list is the explicit auxiliary storage used by the shown code.

Interview follow-up Questions

Yes. Equal salaries are handled by comparing experience values, so the employee record with lower experience appears earlier.

Sorting

Read Similar Blogs

SortingBinary Search TreeData StructuresRecursion

Search in a Binary Search Tree

In the Search in a Binary Search Tree problem, you are given the root node of a binary search tree and an integer target value. Your task is to find the specific node in the tree wher...

70.6k
ArraysStringHashingSorting

Group Anagrams

Given an array strs containing N strings made of lowercase English letters, place all anagrams inside the same group. Anagrams contain identical character frequencies, although character order may...

59.1k
Two PointerBinary SearchMathsSortingArrays

Median of 2 Sorted Arrays

tuf-examples-1 Input : nums1 = [1, 3], nums2 = [2] Output : 2.00000 Explanation : The combined sorted array is [1, 2, 3]. The middle element is 2, so the median is 2.0. Input : nums1 = [1, 2], nums...

79.5k
Comments0