Sort Students by Marks then Name

81.1k
0

A list of student records is given. Each record contains a student name and a marks value. Rearrange the complete list in non-decreasing order of marks.

If two students have equal marks, arrange such students in lexicographical order of names. Return the sorted list of student records.

Example 1

Input: students = [["Aman", 88], ["Riya", 95], ["Kabir", 88], ["Meera", 70]]
Output: [["Meera", 70], ["Aman", 88], ["Kabir", 88], ["Riya", 95]]
Explanation: Marks are ordered as 70, 88, 88, and 95. Equal marks 88 are arranged by name, so Aman appears before Kabir.

Example 2

Input: students = [["Zara", 91]]
Output: [["Zara", 91]]
Explanation: A single student record already satisfies the required order.

Brute Force Approach

The easiest observation is small but useful: a student record should move left only when a previous record has larger marks, or when equal marks have a larger name. The name and marks must travel together, so every record stays complete during movement.

A stable insertion process keeps a sorted prefix. The next student is saved, larger records shift one position right, and the saved student is placed into the open position. Equal marks are handled carefully through the name comparison.

The idea feels friendly for learning because each pass answers one local question: does the saved student belong before the current prefix student?

Algorithm

  • A copied list named answer is created so the original student list remains unchanged outside the method.

  • The number of students is stored in n so every record after the first record can be inserted into the sorted prefix.

  • Every index from 1 through n - 1 is treated as the next student record needing a correct position inside the prefix.

  • The current student record is saved, and position is placed at the previous prefix index.

  • Prefix records are shifted right while marks are larger, or while equal marks have a lexicographically larger name.

  • The saved student record is placed after the last record having smaller marks or an equal-valid name order.

  • The sorted copy is returned after every student record has been inserted into the prefix.

Dry Run

Sort Students by Marks, Then by Name - Brute Force Approach

Sort Students by Marks, Then by Name - Brute Force Approach

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Sorts student records through stable insertion by marks and name.
vector<pair<string, int>> sortStudents(vector<pair<string, int>>& students) {
vector<pair<string, int>> answer = students;
int n = answer.size();
// Each pass inserts one record into the sorted prefix.
for (int index = 1; index < n; index++) {
pair<string, int> currentStudent = answer[index];
int position = index - 1;
// Larger marks or larger names for equal marks must move right.
while (position >= 0 && shouldMoveRight(answer[position], currentStudent)) {
answer[position + 1] = answer[position];
position--;
}
// The saved record is placed after every valid earlier record.
answer[position + 1] = currentStudent;
}
return answer;
}
private:
// Checks whether the left record belongs after the right record.
bool shouldMoveRight(pair<string, int> left, pair<string, int> right) {
// Larger marks must appear later in non-decreasing marks order.
if (left.second > right.second) {
return true;
}
// Equal marks are ordered by lexicographical name.
if (left.second == right.second && left.first > right.first) {
return true;
}
return false;
}
};
// Driver code
int main() {
// Input array
vector<pair<string, int>> students = {{"Aman", 88}, {"Riya", 95}, {"Kabir", 88}, {"Meera", 70}};
// Solution object creation
Solution obj;
// Result printing
vector<pair<string, int>> answer = obj.sortStudents(students);
for (int index = 0; index < answer.size(); index++) {
cout << "[" << answer[index].first << ", " << answer[index].second << "]";
// A separator is printed between neighboring records.
if (index + 1 < answer.size()) {
cout << " ";
}
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the number of student records, because each student record can be compared with all earlier records during insertion.

Space Complexity: O(N), because a copied list of student records is maintained before sorting.

Better Approach

Stable insertion can shift many student records one position at a time. Merge sort reduces repeated movement by splitting the list into smaller ranges, sorting both halves, and joining the sorted halves in linear passes.

During each merge, marks are checked first and names are checked only for equal marks. The earlier record moves directly into temporary storage. Equal marks and equal names choose the left record, so completely identical ordering keys keep original relative order without a sorting callback.

Algorithm

  • Begin with a copied list named answer and a temporary list of equal size, so complete student records can move without changing the caller-owned list.

  • Start merge sort on the full index range because every student record belongs to the final marks-and-name order.

  • Stop a recursive call at a range containing at most one record because a single record already forms a sorted range.

  • Split every larger range at the middle index and sort both halves recursively, so each merge receives two correctly ordered ranges.

  • Compare current records by marks first and names after equal marks, so the exact primary and secondary rules are applied directly.

  • Move the earlier record into the temporary list and copy every remaining record after one half finishes, so no name-marks pair becomes separated or skipped.

  • Copy the merged range back into answer, so completed ranges can support larger merges, and return answer after the full range becomes sorted.

Dry Run

Sort Students by Marks then by Name better appraoch

Sort Students by Marks then by Name better appraoch

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Merges two ranges by marks and name.
void mergeRanges(vector<pair<string, int>>& answer,
vector<pair<string, int>>& temp,
int left, int middle, int right) {
int leftIndex = left;
int rightIndex = middle + 1;
int writeIndex = left;
// Current records provide the next student.
while (leftIndex <= middle && rightIndex <= right) {
// Direct field checks choose the earlier student.
if (answer[leftIndex].second <
answer[rightIndex].second ||
(answer[leftIndex].second ==
answer[rightIndex].second &&
answer[leftIndex].first <=
answer[rightIndex].first)) {
temp[writeIndex] = answer[leftIndex];
leftIndex++;
} else {
temp[writeIndex] = answer[rightIndex];
rightIndex++;
}
writeIndex++;
}
// Remaining left records keep sorted order.
while (leftIndex <= middle) {
temp[writeIndex] = answer[leftIndex];
leftIndex++;
writeIndex++;
}
// Remaining right records keep sorted order.
while (rightIndex <= right) {
temp[writeIndex] = answer[rightIndex];
rightIndex++;
writeIndex++;
}
// The merged range replaces the old range.
for (int index = left; index <= right; index++) {
answer[index] = temp[index];
}
}
// Sorts one student range through merge sort.
void mergeSort(vector<pair<string, int>>& answer,
vector<pair<string, int>>& temp,
int left, int right) {
// A one-record range already has sorted order.
if (left >= right) {
return;
}
int middle = left + (right - left) / 2;
// Both halves become sorted before merging.
mergeSort(answer, temp, left, middle);
mergeSort(answer, temp, middle + 1, right);
// Two sorted halves form one sorted range.
mergeRanges(answer, temp, left, middle, right);
}
public:
// Sorts a copy through direct merge sort.
vector<pair<string, int>> sortStudents(
vector<pair<string, int>>& students) {
vector<pair<string, int>> answer = students;
int n = answer.size();
vector<pair<string, int>> temp(n);
// A larger list needs recursive splitting.
if (n > 1) {
mergeSort(answer, temp, 0, n - 1);
}
return answer;
}
};
// Driver code
int main() {
vector<pair<string, int>> students = {
{"Aman", 88}, {"Riya", 95},
{"Kabir", 88}, {"Meera", 70}
};
Solution obj;
vector<pair<string, int>> answer = obj.sortStudents(students);
for (pair<string, int> student : answer) {
cout << "[" << student.first << ", "
<< student.second << "] ";
}
cout << endl;
return 0;
}

Complexity Analysis

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

Space Complexity: O(N), the temporary list stores N records while the recursion stack uses O(log N) additional space.

Optimal Approach

Manual insertion shows the ordering rule clearly, but shifting records one by one becomes slow for large lists. A built-in sorting routine already knows how to arrange records efficiently. The only missing piece is the comparison rule.

The comparator checks marks first. Smaller marks must come earlier. When marks match, names decide the order, giving a predictable result for every tie.

The solution becomes calm and direct: keep each student record whole, then give the sorting routine a rule for choosing the earlier record.

Algorithm

  • A copied list named answer is created so the original student list remains unchanged outside the method.

  • A comparator or sorting key is prepared to compare student records by marks first.

  • Name comparison is used only when marks are equal, so ties become deterministic.

  • The built-in sorting routine is applied to answer with the custom comparison rule.

  • During sorting, complete student records are rearranged while names and marks remain together.

  • The sorted list is returned after the sorting routine finishes all required comparisons.

Dry Run

Image 1

Image 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Sorts student records by marks first and name second.
vector<pair<string, int>> sortStudents(vector<pair<string, int>>& students) {
vector<pair<string, int>> answer = students;
sort(answer.begin(), answer.end(), [](pair<string, int> left, pair<string, int> right) {
// Equal marks are ordered by lexicographical name.
if (left.second == right.second) {
return left.first < right.first;
}
return left.second < right.second;
});
return answer;
}
};
// Driver code
int main() {
// Input array
vector<pair<string, int>> students = {{"Aman", 88}, {"Riya", 95}, {"Kabir", 88}, {"Meera", 70}};
// Solution object creation
Solution obj;
// Result printing
vector<pair<string, int>> answer = obj.sortStudents(students);
for (int index = 0; index < answer.size(); index++) {
cout << "[" << answer[index].first << ", " << answer[index].second << "]";
// A separator is printed between neighboring records.
if (index + 1 < answer.size()) {
cout << " ";
}
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), because comparison sorting arranges N student records through logarithmic-depth comparison work.

Space Complexity: O(N), because a copied list of student records is maintained before sorting. Extra internal sorting storage depends on the language runtime.

Interview follow-up Questions

The common comparator variant sorts marks in non-decreasing order. Descending marks require reversing the marks comparison while keeping name comparison unchanged or adjusted according to the requested tie rule.

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 charac...

59.1k
Two PointerBinary SearchMathsSortingArrays

Median of 2 Sorted Arrays

Given two sorted arrays nums1 and nums2 of size M and N respectively, return the median of the two sorted arrays. The final array is formed by merging both arrays and sorting them in non-decreasing...

79.5k
Comments0